51 lines
1.5 KiB
Text
51 lines
1.5 KiB
Text
var input="3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
|
|
|
|
var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc)
|
|
"/",T(3,False), "+",T(2,False), "-",T(2,False),
|
|
);
|
|
|
|
"infix: ".println(input);
|
|
"postfix:".println(parseInfix(input));
|
|
|
|
fcn parseInfix(e){
|
|
stack:=List(); // holds operators and left parenthesis
|
|
rpn:="";
|
|
foreach tok in (e.split(" ")){
|
|
switch(tok){
|
|
case("("){ stack.append(tok) } // push "(" to stack
|
|
case(")"){
|
|
while(True){ // pop item ("(" or operator) from stack
|
|
op:=stack.pop();
|
|
if(op=="(") break; // discard "("
|
|
rpn+=" " + op; // add operator to result
|
|
}
|
|
}
|
|
else{ // default
|
|
o1:=opa.find(tok); // op or Void
|
|
if(o1){ // token is an operator
|
|
while(stack){
|
|
// consider top item on stack
|
|
op:=stack[-1]; o2:=opa.find(op);
|
|
if(not o2 or o1[0]>o2[0] or
|
|
(o1[0]==o2[0] and o1[1])) break;
|
|
// top item is an operator that needs to come off
|
|
stack.pop();
|
|
rpn+=" " + op; // add it to result
|
|
}
|
|
// push operator (the new one) to stack
|
|
stack.append(tok);
|
|
}else // token is an operand
|
|
rpn+=(rpn and " " or "") + tok; // add operand to result
|
|
}
|
|
} // switch
|
|
display(tok,rpn,stack);
|
|
} // foreach
|
|
// drain stack to result
|
|
rpn + stack.reverse().concat(" ");
|
|
}
|
|
fcn display(tok,rpn,stack){
|
|
"Token|".println(tok);
|
|
"Stack|".println(stack.concat());
|
|
"Queue|".println(rpn);
|
|
println();
|
|
}
|