Back to index

wims  3.65+svn20090927
RPN.java
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2007-2008 Mihai Preda.
00003  *
00004  * Licensed under the Apache License, Version 2.0 (the "License");
00005  * you may not use this file except in compliance with the License.
00006  * You may obtain a copy of the License at
00007  *
00008  *      http://www.apache.org/licenses/LICENSE-2.0
00009  *
00010  * Unless required by applicable law or agreed to in writing, software
00011  * distributed under the License is distributed on an "AS IS" BASIS,
00012  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  * See the License for the specific language governing permissions and
00014  * limitations under the License.
00015  */
00016 
00017 package org.javia.arity;
00018 
00019 import java.util.Stack;
00020 import java.util.EmptyStackException;
00021 
00022 /* Reverse Polish Notation
00023    reads tokens in normal infix order (e.g.: 1 + 2)
00024    and outputs them in Reverse Polish order (e.g.: 1 2 +).
00025    See Dijkstra's Shunting Yard algorithm: 
00026    http://en.wikipedia.org/wiki/Shunting_yard_algorithm
00027  */ 
00028 class RPN extends TokenConsumer {
00029     Stack stack = new Stack();
00030     int prevTokenId = 0;
00031     TokenConsumer consumer;
00032     SyntaxException exception;
00033 
00034     RPN(SyntaxException exception) {
00035         this.exception = exception;
00036     }
00037 
00038     void setConsumer(TokenConsumer consumer) {
00039         this.consumer = consumer;
00040     }
00041 
00042     //@Override
00043     void start() {
00044         stack.removeAllElements();
00045         prevTokenId = 0;
00046         consumer.start();
00047     }
00048 
00049     private Token top() {
00050         return stack.empty() ? null : (Token) stack.peek();
00051     }
00052 
00053     private void popHigher(int priority) throws SyntaxException {
00054         Token t = top();
00055         while (t != null && t.priority >= priority) {
00056             consumer.push(t);
00057             //code.push(t);
00058             stack.pop();
00059             t = top();
00060         }
00061     }
00062 
00063     static final boolean isOperand(int id) {
00064         return 
00065             id == Lexer.FACT || 
00066             id == Lexer.RPAREN ||
00067             id == Lexer.NUMBER ||
00068             id == Lexer.CONST;
00069     }
00070 
00071     void push(Token token) throws SyntaxException {
00072         int priority = token.priority;
00073         int id = token.id;
00074         switch (id) {
00075         case Lexer.NUMBER:
00076         case Lexer.CONST:
00077             if (isOperand(prevTokenId)) {
00078                 push(Lexer.TOK_MUL);
00079             }
00080             consumer.push(token);
00081             break;
00082             
00083             /*
00084         case Lexer.CALL:
00085         case Lexer.LPAREN:
00086             if (isOperand(prevTokenId)) {
00087                 push(Lexer.TOK_MUL);
00088             }
00089             stack.push(token);
00090             break;
00091             */
00092             
00093         case Lexer.RPAREN: {
00094             if (prevTokenId == Lexer.CALL) {
00095                 top().arity--;
00096             } else if (!isOperand(prevTokenId)) {
00097                 throw exception.set("unexpected ) or END", token.position);
00098             }
00099 
00100             popHigher(priority);
00101             Token t = top();
00102             if (t != null) {
00103                 if (t.id == Lexer.CALL) {
00104                     consumer.push(t);
00105                 } else if (t != Lexer.TOK_LPAREN) {
00106                     throw exception.set("expected LPAREN or CALL", token.position);
00107                 }
00108                 stack.pop();
00109             }
00110             break;
00111         }
00112         
00113         case Lexer.COMMA: {            
00114             if (!isOperand(prevTokenId)) {
00115                 throw exception.set("misplaced COMMA", token.position);
00116             }
00117             popHigher(priority);
00118             Token t = top();
00119             if (t==null || t.id != Lexer.CALL) {
00120                 throw exception.set("COMMA not inside CALL", token.position);
00121             }
00122             t.arity++;
00123             //code.push(stack.pop());
00124             break;
00125         }
00126         
00127         case Lexer.END: {
00128             Token t = Lexer.TOK_RPAREN;
00129             t.position = token.position;
00130             do {
00131                 push(t);
00132             } while (top() != null);
00133             break;
00134         }
00135             
00136         default: //operators, CALL, LPAREN
00137             if (token.assoc == Token.PREFIX) {
00138                 if (isOperand(prevTokenId)) {
00139                     push(Lexer.TOK_MUL);
00140                 }
00141                 stack.push(token);
00142                 break;
00143             }
00144             if (!isOperand(prevTokenId)) {
00145                 if (id == Lexer.SUB) {
00146                     //change SUB to unary minus
00147                     token = Lexer.TOK_UMIN;
00148                     stack.push(token);
00149                     break;
00150                 } else if (id == Lexer.ADD) {
00151                     // ignore, keep prevTokenId unchanged
00152                     return;
00153                 }
00154                 throw exception.set("operator without operand", token.position);
00155             }
00156             popHigher(priority + (token.assoc == Token.RIGHT ? 1 : 0));
00157             stack.push(token);
00158         }
00159         prevTokenId = token.id;
00160     }
00161 }