Parsing/Shunting-yard algorithm: Difference between revisions
m (added whitespace before the TOC (table of contents).) |
(→{{header|REXX}}: added/changed comments and whitespace, changed indentations, simplified some code.) |
||
Line 2,196: | Line 2,196: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
These versions |
These REXX versions below allow multi-character tokens (both operands and operators). |
||
===assume expression is correct=== |
===assume expression is correct=== |
||
<lang rexx>/*REXX |
<lang rexx>/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/ |
||
parse arg x |
parse arg x /*obtain optional argument from the CL.*/ |
||
if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ |
|||
ox=x |
|||
x='(' space(x) ') '; tokens=words(x) /*force stacking for the expression. */ |
|||
x='(' space(x) ") " /*force stacking for the expression. */ |
|||
#=words(x) /*get number of tokens in expression. */ |
|||
do i=1 for #; @.i=word(x, i) /*assign the input tokens to an array. */ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
L=max( 20, length(x) ) /*use twenty for the minimum show width*/ |
|||
⚫ | |||
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/ |
|||
center("output", L, '─') center("action", L, '─') |
|||
op= ")(-+/*^"; Rop=substr(op,3); p.=; n=length(op); RPN= /*some handy-dandy vars.*/ |
|||
s.= |
|||
⚫ | |||
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/ |
|||
$= /* [↑] assign the operator priorities.*/ |
|||
do k=1 for #; ?=@.k /*process each token from the @. list.*/ |
|||
select /*@.k is: (, operator, ), operand*/ |
|||
when ?=='(' then do; $="(" $; call show 'moving' ? "──► stack"; end |
|||
when isOp(?) then do; !=word($, 1) /*get token from stack*/ |
|||
do while ! \==')' & s.!>=p.? |
|||
RPN=RPN ! /*add token to RPN.*/ |
|||
$=subword($, 2) /*del token from stack*/ |
|||
call show 'unstacking:' ! |
|||
!=word($, 1) /*get token from stack*/ |
|||
end /*while*/ |
|||
$= |
$=? $ /*add token to stack*/ |
||
call show 'moving' ? "──► stack" |
|||
end |
|||
when ?==')' then do; !=word($, 1) /*get token from stack*/ |
|||
do while !\=='('; RPN=RPN ! /*add token to RPN. */ |
|||
$=subword($, 2) /*del token from stack*/ |
|||
!= word($, 1) /*get token from stack*/ |
|||
call show 'moving stack' ! "──► RPN" |
|||
end /*while*/ |
|||
⚫ | |||
call show 'deleting ( from the stack' |
|||
end |
|||
⚫ | |||
⚫ | |||
end /*select*/ |
end /*select*/ |
||
end /*k*/ |
|||
say |
|||
⚫ | |||
RPN=space(RPN $) |
|||
say |
say ' input:' ox; say " RPN──►" RPN /*display the input and the RPN. */ |
||
parse source upper . y . /*invoked via the C.L. or REXX pgm? */ |
parse source upper . y . /*invoked via the C.L. or REXX pgm? */ |
||
if y=='COMMAND' then exit /*stick a fork in it, we're all done. */ |
if y=='COMMAND' then exit /*stick a fork in it, we're all done. */ |
||
else return RPN /*return RPN to invoker (the RESULT). */ |
else return RPN /*return RPN to invoker (the RESULT). */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
isOp: return pos(arg(1),rOp)\==0 /*is |
isOp: return pos(arg(1),rOp) \== 0 /*is the first argument a "real" operator? */ |
||
⚫ | |||
/*─────────────────────────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
'''output''' when using the default input: |
'''output''' when using the default input: |
||
<pre> |
<pre> |
||
Line 2,283: | Line 2,289: | ||
The '''select''' group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source. |
The '''select''' group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source. |
||
<lang rexx>/*REXX |
<lang rexx>/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/ |
||
parse arg x |
parse arg x /*obtain optional argument from the CL.*/ |
||
if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ |
|||
g=0 /* G is a counter of ( and ) */ |
|||
do p=1 for words(x); _=word(x,p) /*catches unbalanced ( ) and ) ( */ |
|||
if _=='(' then g=g+1 |
|||
if _=='(' then g=g+1 |
|||
else if _==')' then do; g=g-1; if g<0 then g=-1e8; end |
|||
⚫ | |||
⚫ | |||
⚫ | |||
ox=x |
|||
⚫ | |||
x='(' space(x) |
x='(' space(x) ") " /*force stacking for the expression. */ |
||
#=words(x) /*get number of tokens in expression. */ |
|||
good= (g==0) /*indicate expression is good or bad.*/ |
|||
do i=1 for #; @.i=word(x, i) /*assign the input tokens to an array. */ |
|||
⚫ | |||
end /*i*/ |
|||
pad=left('',5); op=')(-+/*^'; rOp=substr(op,3); p.=; n=length(op); s.=; RPN=; $= |
|||
tell=1 /*set to 0 if working steps not wanted.*/ |
|||
L=max( 20, length(x) ) /*use twenty for the minimum show width*/ |
|||
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/ |
|||
⚫ | |||
⚫ | |||
center("output", L, '─') center("action", L, '─') |
|||
do #=1 for tokens*good; ?=@.# /*process each token from the @. list.*/ |
|||
⚫ | |||
⚫ | |||
s.= |
|||
⚫ | |||
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/ |
|||
$= /* [↑] assign the operator priorities.*/ |
|||
do k=1 for #*good; ?=@.k /*process each token from the @. list.*/ |
|||
select /*@.k is: ( operator ) operand.*/ |
|||
when ?=='(' then do; $="(" $; call show 'moving' ? "──► stack"; end |
|||
when isOp(?) then do; !=word($, 1) /*get token from stack*/ |
|||
do while ! \==')' & s.!>=p.? |
|||
RPN=RPN ! /*add token to RPN.*/ |
|||
$=subword($, 2) /*del token from stack*/ |
|||
call show 'unstacking:' ! |
|||
!=word($, 1) /*get token from stack*/ |
|||
end /*while*/ |
|||
$=? $ /*add token to stack*/ |
|||
call show 'moving |
call show 'moving' ? "──► stack" |
||
end |
end |
||
when ?==')' then do; !=word($, 1) /*get token from stack*/ |
|||
do while !\=='('; RPN=RPN ! /*add token to RPN.*/ |
|||
$=subword($, 2) /*del token from stack*/ |
|||
!= word($, 1) /*get token from stack*/ |
|||
call show 'moving' |
call show 'moving stack' ! "──► RPN" |
||
end /* |
end /*while*/ |
||
$=subword($, 2) /*del token from stack*/ |
|||
⚫ | |||
call show 'deleting ( from the stack' |
|||
end |
|||
RPN=space(RPN $) |
|||
⚫ | |||
⚫ | |||
call show 'moving' ? "──► RPN" |
|||
end /*select*/ |
|||
⚫ | |||
end /*k*/ |
|||
⚫ | |||
say |
|||
⚫ | |||
⚫ | |||
/*────────────────────────────────────────────────────────────────────────────*/ |
|||
say ' input:' ox; say " RPN──►" RPN /*display the input and the RPN. */ |
|||
⚫ | |||
⚫ | |||
/*─────────────────────────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
/*──────────────────────────────────────────────────────────────────────────────────────────*/ |
|||
⚫ | |||
⚫ | |||
'''output''' when using the input: <tt> ) ( </tt> |
'''output''' when using the input: <tt> ) ( </tt> |
||
<pre> |
<pre> |
Revision as of 09:22, 13 April 2016
You are encouraged to solve this task according to the task description, using any language you may know.
Given the operator characteristics and input from the Shunting-yard algorithm page and tables Use the algorithm to show the changes in the operator stack and RPN output as each individual token is processed.
- Assume an input of a correct, space separated, string of tokens representing an infix expression
- Generate a space separated output string representing the RPN
- Test with the input string
'3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
then print and display the output here. - Operator precedence is given in this table:
operator precedence associativity ^ 4 Right * 3 Left / 3 Left + 2 Left - 2 Left
- Extra credit
- Add extra text explaining the actions and an optional comment for the action on receipt of each token.
- Note
- the handling of functions and arguments is not required.
- See also
- Parsing/RPN calculator algorithm for a method of calculating a final value from this output RPN expression.
- Parsing/RPN to infix conversion.
AutoHotkey
<lang AHK>SetBatchLines -1
- NoEnv
expr := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
output := "Testing string '" expr "'`r`n`r`nToken`tOutput Queue"
. Space(StrLen(expr)-StrLen("Output Queue")+2) "OP Stack"
- define a stack with semantic .push() and .pop() funcs
stack := {push: func("ObjInsert"), pop: func("ObjRemove"), peek: func("Peek")}
Loop Parse, expr, %A_Space% {
token := A_LoopField if token is number Q .= token A_Space if isOp(token){ o1 := token while isOp(o2 := stack.peek()) and ((isLeft(o1) and Precedence(o1) <= Precedence(o2)) or (isRight(o1) and Precedence(o1) < Precedence(o2))) Q .= stack.pop() A_Space stack.push(o1) } If ( token = "(" ) stack.push(token) If ( token = ")" ) { While ((t := stack.pop()) != "(") && (t != "") Q .= t A_Space if (t = "") throw Exception("Unmatched parenthesis. " . "Character number " A_Index) } output .= "`r`n" token Space(7) Q Space(StrLen(expr)+2-StrLen(Q)) . Disp(stack)
} output .= "`r`n(empty stack to output)" While (t := stack.pop()) != ""
if InStr("()", t) throw Exception("Unmatched parenthesis.") else Q .= t A_Space, output .= "`r`n" Space(8) Q . Space(StrLen(expr)+2-StrLen(Q)) Disp(stack)
output .= "`r`n`r`nFinal string: '" Q "'" clipboard := output
isOp(t){
return (!!InStr("+-*/^", t) && t)
} Peek(this){
r := this.Remove(), this.Insert(r) return r
} IsLeft(o){
return !!InStr("*/+-", o)
} IsRight(o){
return o = "^"
} Precedence(o){
return (InStr("+-/*^", o)+3)//2
} Disp(obj){
for each, val in obj o := val . o return o
} Space(n){
return n>0 ? A_Space Space(n-1) : ""
}</lang>
- Output
Testing string '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' Token Output Queue OP Stack 3 3 + 3 + 4 3 4 + * 3 4 *+ 2 3 4 2 *+ / 3 4 2 * /+ ( 3 4 2 * (/+ 1 3 4 2 * 1 (/+ - 3 4 2 * 1 -(/+ 5 3 4 2 * 1 5 -(/+ ) 3 4 2 * 1 5 - /+ ^ 3 4 2 * 1 5 - ^/+ 2 3 4 2 * 1 5 - 2 ^/+ ^ 3 4 2 * 1 5 - 2 ^^/+ 3 3 4 2 * 1 5 - 2 3 ^^/+ (empty stack to output) 3 4 2 * 1 5 - 2 3 ^ ^/+ 3 4 2 * 1 5 - 2 3 ^ ^ /+ 3 4 2 * 1 5 - 2 3 ^ ^ / + 3 4 2 * 1 5 - 2 3 ^ ^ / + Final string: '3 4 2 * 1 5 - 2 3 ^ ^ / + '
C
Requires a functioning ANSI terminal and Enter key. <lang c>#include <sys/types.h>
- include <regex.h>
- include <stdio.h>
typedef struct { const char *s; int len, prec, assoc; } str_tok_t;
typedef struct { const char * str; int assoc, prec; regex_t re; } pat_t;
enum assoc { A_NONE, A_L, A_R }; pat_t pat_eos = {"", A_NONE, 0};
pat_t pat_ops[] = { {"^\\)", A_NONE, -1}, {"^\\*\\*", A_R, 3}, {"^\\^", A_R, 3}, {"^\\*", A_L, 2}, {"^/", A_L, 2}, {"^\\+", A_L, 1}, {"^-", A_L, 1}, {0} };
pat_t pat_arg[] = { {"^[-+]?[0-9]*\\.?[0-9]+([eE][-+]?[0-9]+)?"}, {"^[a-zA-Z_][a-zA-Z_0-9]*"}, {"^\\(", A_L, -1}, {0} };
str_tok_t stack[256]; /* assume these are big enough */ str_tok_t queue[256]; int l_queue, l_stack;
- define qpush(x) queue[l_queue++] = x
- define spush(x) stack[l_stack++] = x
- define spop() stack[--l_stack]
void display(const char *s) { int i; printf("\033[1;1H\033[JText | %s", s); printf("\nStack| "); for (i = 0; i < l_stack; i++) printf("%.*s ", stack[i].len, stack[i].s); // uses C99 format strings printf("\nQueue| "); for (i = 0; i < l_queue; i++) printf("%.*s ", queue[i].len, queue[i].s); puts("\n\n<press enter>"); getchar(); }
int prec_booster;
- define fail(s1, s2) {fprintf(stderr, "[Error %s] %s\n", s1, s2); return 0;}
int init(void) { int i; pat_t *p;
for (i = 0, p = pat_ops; p[i].str; i++) if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED)) fail("comp", p[i].str);
for (i = 0, p = pat_arg; p[i].str; i++) if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED)) fail("comp", p[i].str);
return 1; }
pat_t* match(const char *s, pat_t *p, str_tok_t * t, const char **e) { int i; regmatch_t m;
while (*s == ' ') s++; *e = s;
if (!*s) return &pat_eos;
for (i = 0; p[i].str; i++) { if (regexec(&(p[i].re), s, 1, &m, REG_NOTEOL)) continue; t->s = s; *e = s + (t->len = m.rm_eo - m.rm_so); return p + i; } return 0; }
int parse(const char *s) { pat_t *p; str_tok_t *t, tok;
prec_booster = l_queue = 0; display(s); while (*s) { p = match(s, pat_arg, &tok, &s); if (!p || p == &pat_eos) fail("parse arg", s);
/* Odd logic here. Don't actually stack the parens: don't need to. */ if (p->prec == -1) { prec_booster += 100; continue; } qpush(tok); display(s);
re_op: p = match(s, pat_ops, &tok, &s); if (!p) fail("parse op", s);
tok.assoc = p->assoc; tok.prec = p->prec;
if (p->prec > 0) tok.prec = p->prec + prec_booster; else if (p->prec == -1) { if (prec_booster < 100) fail("unmatched )", s); tok.prec = prec_booster; }
while (l_stack) { t = stack + l_stack - 1; if (!(t->prec == tok.prec && t->assoc == A_L) && t->prec <= tok.prec) break; qpush(spop()); display(s); }
if (p->prec == -1) { prec_booster -= 100; goto re_op; }
if (!p->prec) { display(s); if (prec_booster) fail("unmatched (", s); return 1; }
spush(tok); display(s); }
return 1; }
int main() { int i; const char *tests[] = { "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3", /* RC mandated: OK */ "123", /* OK */ "3+4 * 2 / ( 1 - 5 ) ^ 2 ^ 3.14", /* OK */ "(((((((1+2+3**(4 + 5))))))", /* bad parens */ "a^(b + c/d * .1e5)!", /* unknown op */ "(1**2)**3", /* OK */ 0 };
if (!init()) return 1; for (i = 0; tests[i]; i++) { printf("Testing string `%s' <enter>\n", tests[i]); getchar();
printf("string `%s': %s\n\n", tests[i], parse(tests[i]) ? "Ok" : "Error"); }
return 0; }</lang>
- Output
Note: This cannot give a flavour of the true interactive output where tokens are shuffled around every time the enter key is pressed.
Testing string `3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' <enter> Text | 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Stack| Queue| <press enter> Text | + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Stack| Queue| 3 <press enter> Text | 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Stack| + Queue| 3 <press enter> Text | * 2 / ( 1 - 5 ) ^ 2 ^ 3 Stack| + Queue| 3 4 <press enter> Text | 2 / ( 1 - 5 ) ^ 2 ^ 3 Stack| + * Queue| 3 4 <press enter> Text | / ( 1 - 5 ) ^ 2 ^ 3 Stack| + * Queue| 3 4 2 <press enter> Text | ( 1 - 5 ) ^ 2 ^ 3 Stack| + Queue| 3 4 2 * <press enter> Text | ( 1 - 5 ) ^ 2 ^ 3 Stack| + / Queue| 3 4 2 * <press enter> Text | - 5 ) ^ 2 ^ 3 Stack| + / Queue| 3 4 2 * 1 <press enter> Text | 5 ) ^ 2 ^ 3 Stack| + / - Queue| 3 4 2 * 1 <press enter> Text | ) ^ 2 ^ 3 Stack| + / - Queue| 3 4 2 * 1 5 <press enter> Text | ^ 2 ^ 3 Stack| + / Queue| 3 4 2 * 1 5 - <press enter> Text | 2 ^ 3 Stack| + / ^ Queue| 3 4 2 * 1 5 - <press enter> Text | ^ 3 Stack| + / ^ Queue| 3 4 2 * 1 5 - 2 <press enter> Text | 3 Stack| + / ^ ^ Queue| 3 4 2 * 1 5 - 2 <press enter> Text | Stack| + / ^ ^ Queue| 3 4 2 * 1 5 - 2 3 <press enter> Text | Stack| + / ^ Queue| 3 4 2 * 1 5 - 2 3 ^ <press enter> Text | Stack| + / Queue| 3 4 2 * 1 5 - 2 3 ^ ^ <press enter> Text | Stack| + Queue| 3 4 2 * 1 5 - 2 3 ^ ^ / <press enter> Text | Stack| Queue| 3 4 2 * 1 5 - 2 3 ^ ^ / + <press enter> Text | Stack| Queue| 3 4 2 * 1 5 - 2 3 ^ ^ / + <press enter> string `3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3': Ok Testing string `123' <enter> ^C
Ceylon
<lang ceylon>import ceylon.collection {
ArrayList }
abstract class Token(String|Integer data) of IntegerLiteral | Operator | leftParen | rightParen { string => data.string; } class IntegerLiteral(shared Integer integer) extends Token(integer) {} class Operator extends Token {
shared Integer precedence; shared Boolean rightAssoc;
shared new plus extends Token("+") { precedence = 2; rightAssoc = false; } shared new minus extends Token("-") { precedence = 2; rightAssoc = false; } shared new times extends Token("*") { precedence = 3; rightAssoc = false; } shared new divides extends Token("/") { precedence = 3; rightAssoc = false; } shared new power extends Token("^") { precedence = 4; rightAssoc = true; }
shared Boolean below(Operator other) => !rightAssoc && precedence <= other.precedence || rightAssoc && precedence < other.precedence; } object leftParen extends Token("(") {} object rightParen extends Token(")") {}
shared void run() {
function shunt(String input) {
function tokenize(String input) => input.split().map((String element) => switch(element.trimmed) case("(") leftParen case(")") rightParen case("+") Operator.plus case("-") Operator.minus case("*") Operator.times case("/") Operator.divides case("^") Operator.power else IntegerLiteral(parseInteger(element) else 0)); // no error handling
value outputQueue = ArrayList<Token>(); value operatorStack = ArrayList<Token>();
void report(String action) { print("``action.padTrailing(22)`` | ``" ".join(outputQueue).padTrailing(25)`` | ``" ".join(operatorStack).padTrailing(10)``"); }
print("input is ``input``\n"); print("Action | Output Queue | Operators' Stack -----------------------|---------------------------|-----------------");
for(token in tokenize(input)) { switch(token) case(is IntegerLiteral) { outputQueue.offer(token); report("``token`` from input to queue"); } case(leftParen) { operatorStack.push(token); report("``token`` from input to stack"); } case(rightParen){ while(exists top = operatorStack.pop(), top != leftParen) { outputQueue.offer(top); report("``top`` from stack to queue"); } } case(is Operator) { while(exists top = operatorStack.top, is Operator top, token.below(top)) { operatorStack.pop(); outputQueue.offer(top); report("``top`` from stack to queue"); } operatorStack.push(token); report("``token`` from input to stack"); } } while(exists top = operatorStack.pop()) { outputQueue.offer(top); report("``top`` from stack to queue"); } return " ".join(outputQueue); }
value rpn = shunt("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"); assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +"); print("\nthe result is ``rpn``"); }</lang>
- Output:
input is 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Action | Output Queue | Operators' Stack -----------------------|---------------------------|----------------- 3 from input to queue | 3 | + from input to stack | 3 | + 4 from input to queue | 3 4 | + * from input to stack | 3 4 | + * 2 from input to queue | 3 4 2 | + * * from stack to queue | 3 4 2 * | + / from input to stack | 3 4 2 * | + / ( from input to stack | 3 4 2 * | + / ( 1 from input to queue | 3 4 2 * 1 | + / ( - from input to stack | 3 4 2 * 1 | + / ( - 5 from input to queue | 3 4 2 * 1 5 | + / ( - - from stack to queue | 3 4 2 * 1 5 - | + / ( ^ from input to stack | 3 4 2 * 1 5 - | + / ^ 2 from input to queue | 3 4 2 * 1 5 - 2 | + / ^ ^ from input to stack | 3 4 2 * 1 5 - 2 | + / ^ ^ 3 from input to queue | 3 4 2 * 1 5 - 2 3 | + / ^ ^ ^ from stack to queue | 3 4 2 * 1 5 - 2 3 ^ | + / ^ ^ from stack to queue | 3 4 2 * 1 5 - 2 3 ^ ^ | + / / from stack to queue | 3 4 2 * 1 5 - 2 3 ^ ^ / | + + from stack to queue | 3 4 2 * 1 5 - 2 3 ^ ^ / + | the result is 3 4 2 * 1 5 - 2 3 ^ ^ / +
Common Lisp
Implemented as a state machine. The current state is the top of both the input queue and the operator stack. A signal function receives the current state and does a lookup to determine the signal to output. Based on the signal, the state (input queue and/or operator stack) is changed. The process iterates until both queue and stack are empty. <lang lisp>;;;; Parsing/infix to RPN conversion (defconstant operators "^*/+-") (defconstant precedence '(-4 3 3 2 2))
(defun operator-p (op)
"string->integer|nil: Returns operator precedence index or nil if not operator." (and (= (length op) 1) (position (char op 0) operators)))
(defun has-priority (op2 op1)
"(string,string)->boolean: True if op2 has output priority over op1." (defun prec (op) (nth (operator-p op) precedence)) (or (and (plusp (prec op1)) (<= (prec op1) (abs (prec op2)))) (and (minusp (prec op1)) (< (- (prec op1)) (abs (prec op2))))))
(defun string-split (expr)
"string->list: Tokenize a space separated string." (let* ((p (position #\Space expr)) (tok (if p (subseq expr 0 p) expr))) (if p (append (list tok) (string-split (subseq expr (1+ p)))) (list tok))))
(defun classify (tok)
"nil|string->symbol: Classify a token." (cond ((null tok) 'NOL) ((operator-p tok) 'OPR) ((string= tok "(") 'LPR) ((string= tok ")") 'RPR) (t 'LIT)))
- transitions when op2 is dont care
(defconstant trans1D '((LIT GO) (LPR ENTER)))
- transitions when we check op2 also
(defconstant trans2D
'((OPR ((NOL ENTER) (LPR ENTER) (OPR (lambda (op1 op2) (if (has-priority op2 op1) 'LEAVE 'ENTER))))) (RPR ((NOL "mismatched parentheses") (LPR CLEAR) (OPR LEAVE))) (NOL ((NOL nil) (LPR "mismatched parentheses") (OPR LEAVE)))))
(defun do-signal (op1 op2)
"(nil|string,nil|string)->symbol|string|nil: Emit a signal based on state of inputq and opstack. A nil return is a successful lookup (on nil,nil) because all input combinations are specified." (let ((sig (or (cadr (assoc (classify op1) trans1D)) (cadr (assoc (classify op2) (cadr (assoc (classify op1) trans2D))))))) (if (or (null sig) (symbolp sig) (stringp sig)) sig (funcall (coerce sig 'function) op1 op2))))
(defun rpn (expr)
"string->string: Parse infix expression into rpn." (format t "TOKEN TOS SIGNAL OPSTACK OUTPUTQ~%") ;; iterate until both stacks empty (do* ((input (string-split expr)) (opstack nil) (outputq "") (sig (do-signal (first input) (first opstack)) (do-signal (first input) (first opstack)))) ((null sig) ; until ;; print last closing frame (format t "~A~7,T~A~14,T~A~25,T~A~38,T~A~%" nil nil nil opstack outputq) (subseq outputq 1)) ; return final infix expression ;; print opening frame (format t "~A~7,T~A~14,T" (first input) (first opstack)) (format t (if (stringp sig) "\"~A\"" "~A") sig) ;; switch state (let ((output (case sig (GO (pop input)) (ENTER (push (pop input) opstack) nil) (LEAVE (pop opstack)) (CLEAR (pop input) (pop opstack) nil) (otherwise (pop input) (pop opstack) (if (stringp sig) sig "unknown signal"))))) (when output (setf outputq (concatenate 'string outputq " " output)))) ;; print closing frame (format t "~25,T~A~38,T~A~%" opstack outputq))) ; end-do
(defun main (&optional (xtra nil))
"nil->[printed rpn expressions]: Main function." (let ((expressions '("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" "( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )" "( ( 3 ^ 4 ) ^ 2 ^ 9 ) ^ 2 ^ 5" "3 + 4 * ( 5 - 6 ) ) 4 * 9"))) (dolist (expr (if xtra expressions (list (car expressions)))) (format t "~%INFIX:\"~A\"~%" expr) (format t "RPN:\"~A\"~%" (rpn expr)))))
</lang>
- Output:
CL-USER(2): (main) INFIX:"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" TOKEN TOS SIGNAL OPSTACK OUTPUTQ 3 NIL GO NIL 3 + NIL ENTER (+) 3 4 + GO (+) 3 4 * + ENTER (* +) 3 4 2 * GO (* +) 3 4 2 / * LEAVE (+) 3 4 2 * / + ENTER (/ +) 3 4 2 * ( / ENTER (( / +) 3 4 2 * 1 ( GO (( / +) 3 4 2 * 1 - ( ENTER (- ( / +) 3 4 2 * 1 5 - GO (- ( / +) 3 4 2 * 1 5 ) - LEAVE (( / +) 3 4 2 * 1 5 - ) ( CLEAR (/ +) 3 4 2 * 1 5 - ^ / ENTER (^ / +) 3 4 2 * 1 5 - 2 ^ GO (^ / +) 3 4 2 * 1 5 - 2 ^ ^ ENTER (^ ^ / +) 3 4 2 * 1 5 - 2 3 ^ GO (^ ^ / +) 3 4 2 * 1 5 - 2 3 NIL ^ LEAVE (^ / +) 3 4 2 * 1 5 - 2 3 ^ NIL ^ LEAVE (/ +) 3 4 2 * 1 5 - 2 3 ^ ^ NIL / LEAVE (+) 3 4 2 * 1 5 - 2 3 ^ ^ / NIL + LEAVE NIL 3 4 2 * 1 5 - 2 3 ^ ^ / + NIL NIL NIL NIL 3 4 2 * 1 5 - 2 3 ^ ^ / + RPN:"3 4 2 * 1 5 - 2 3 ^ ^ / +" NIL
EchoLisp
<lang scheme> (require 'hash) (require 'tree)
(define OPS (make-hash)) (hash-set OPS "^" '( 4 #f)) ;; right assoc (hash-set OPS "*" '( 3 #t)) ;; left assoc (hash-set OPS "/" '( 3 #t)) (hash-set OPS "+" '( 2 #t)) (hash-set OPS "-" '( 2 #t))
- helpers
(define (is-right-par? token) (string=? token ")")) (define (is-left-par? token) (string=? token "(")) (define (is-num? op) (not (hash-ref OPS op))) ;; crude (define (is-op? op) (hash-ref OPS op)) (define (is-left? op) (second (hash-ref OPS op))) (define (is-right? op) (not (is-left? op))) (define (op-prec op) (first (hash-ref OPS op)))
- Wikipedia algorithm, translated as it is
(define (shunt tokens S Q)
(for ((token tokens)) (writeln "S: " (stack->list S) "Q: " (queue->list Q) "token: "token) (cond [(is-left-par? token) (push S token) ] [(is-right-par? token) (while (and (stack-top S) (not (is-left-par? (stack-top S)))) (q-push Q ( pop S))) (when (stack-empty? S) (error 'misplaced-parenthesis "()" )) (pop S)] ; // left par [(is-op? token) (while (and (is-op? (stack-top S)) (or (and (is-left? token) (<= (op-prec token) (op-prec (stack-top S)))) (and (is-right? token) (< (op-prec token) (op-prec (stack-top S)))))) (q-push Q (pop S))) (push S token)] [(is-num? token) (q-push Q token)] [else (error 'bad-token token)])) ; for (while (stack-top S) (q-push Q (pop S))))
(string-delimiter "") (define (task infix)
(define S (stack 'S)) (define Q (queue 'Q)) (shunt (text-parse infix) S Q) (writeln 'infix infix) (writeln 'RPN (queue->list Q)))
</lang>
- Output:
(task "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3") S: null Q: null token: 3 S: null Q: (3) token: + S: (+) Q: (3) token: 4 S: (+) Q: (3 4) token: * S: (+ *) Q: (3 4) token: 2 S: (+ *) Q: (3 4 2) token: / S: (+ /) Q: (3 4 2 *) token: ( S: (+ / () Q: (3 4 2 *) token: 1 S: (+ / () Q: (3 4 2 * 1) token: - S: (+ / (-) Q: (3 4 2 * 1) token: 5 S: (+ / (-) Q: (3 4 2 * 1 5) token: ) S: (+ /) Q: (3 4 2 * 1 5 -) token: ^ S: (+ / ^) Q: (3 4 2 * 1 5 -) token: 2 S: (+ / ^) Q: (3 4 2 * 1 5 - 2) token: ^ S: (+ / ^ ^) Q: (3 4 2 * 1 5 - 2) token: 3 infix 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 RPN (3 4 2 * 1 5 - 2 3 ^ ^ / +)
Go
No error checking. No extra credit output, but there are some comments in the code. <lang go>package main
import (
"fmt" "strings"
)
var input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
var opa = map[string]struct {
prec int rAssoc bool
}{
"^": {4, true}, "*": {3, false}, "/": {3, false}, "+": {2, false}, "-": {2, false},
}
func main() {
fmt.Println("infix: ", input) fmt.Println("postfix:", parseInfix(input))
}
func parseInfix(e string) (rpn string) {
var stack []string // holds operators and left parenthesis for _, tok := range strings.Fields(e) { switch tok { case "(": stack = append(stack, tok) // push "(" to stack case ")": var op string for { // pop item ("(" or operator) from stack op, stack = stack[len(stack)-1], stack[:len(stack)-1] if op == "(" { break // discard "(" } rpn += " " + op // add operator to result } default: if o1, isOp := opa[tok]; isOp { // token is an operator for len(stack) > 0 { // consider top item on stack op := stack[len(stack)-1] if o2, isOp := opa[op]; !isOp || o1.prec > o2.prec || o1.prec == o2.prec && o1.rAssoc { break } // top item is an operator that needs to come off stack = stack[:len(stack)-1] // pop it rpn += " " + op // add it to result } // push operator (the new one) to stack stack = append(stack, tok) } else { // token is an operand if rpn > "" { rpn += " " } rpn += tok // add operand to result } } } // drain stack to result for len(stack) > 0 { rpn += " " + stack[len(stack)-1] stack = stack[:len(stack)-1] } return
}</lang> Output:
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Haskell
Simple with zero error handling; some extra credit.
<lang Haskell>import Text.Printf
prec "^" = 4 prec "*" = 3 prec "/" = 3 prec "+" = 2 prec "-" = 2
leftAssoc "^" = False leftAssoc _ = True
isOp (t:[]) = t `elem` "-+/*^" isOp _ = False
simSYA xs = final ++ [lastStep]
where final = scanl f ([],[],"") xs lastStep = (\(x,y,_) -> (reverse y ++ x, [], "")) $ last final f (out,st,_) t | isOp t = (reverse (takeWhile testOp st) ++ out , (t:) $ (dropWhile testOp st), t) | t == "(" = (out, "(":st, t) | t == ")" = (reverse (takeWhile (/="(") st) ++ out, tail $ dropWhile (/="(") st, t) | otherwise = (t:out, st, t) where testOp x = isOp x && (leftAssoc t && prec t == prec x || prec t < prec x)
main = do
a <- getLine printf "%30s%20s%7s" "Output" "Stack" "Token" mapM_ (\(x,y,z) -> printf "%30s%20s%7s\n" (unwords $ reverse x) (unwords y) z) $ simSYA $ words a</lang>
Output:
>main 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Output Stack Token 3 3 3 + + 3 4 + 4 3 4 * + * 3 4 2 * + 2 3 4 2 * / + / 3 4 2 * ( / + ( 3 4 2 * 1 ( / + 1 3 4 2 * 1 - ( / + - 3 4 2 * 1 5 - ( / + 5 3 4 2 * 1 5 - / + ) 3 4 2 * 1 5 - ^ / + ^ 3 4 2 * 1 5 - 2 ^ / + 2 3 4 2 * 1 5 - 2 ^ ^ / + ^ 3 4 2 * 1 5 - 2 3 ^ ^ / + 3 3 4 2 * 1 5 - 2 3 ^ ^ / +
A more complete version with typed input, output and stack; StateT + Control.Lens for stateful actions; Either for both invalid tokens on parsing and unmatched parens when converting; readLine support.
<lang Haskell>{-# LANGUAGE LambdaCase #-} import Control.Applicative import Control.Lens import Control.Monad import Control.Monad.Error import Control.Monad.State import System.Console.Readline
data InToken = InOp Op | InVal Int | LParen | RParen deriving (Show) data OutToken = OutOp Op | OutVal Int data StackElem = StOp Op | Paren deriving (Show) data Op = Pow | Mul | Div | Add | Sub deriving (Show) data Assoc = L | R deriving (Eq)
type Env = ([OutToken], [StackElem]) type RPNComp = StateT Env (Either String)
instance Show OutToken where
show (OutOp x) = snd $ opInfo x show (OutVal v) = show v
opInfo = \case
Pow -> (4, "^") Mul -> (3, "*") Div -> (3, "/") Add -> (2, "+") Sub -> (2, "-")
prec = fst . opInfo leftAssoc Pow = False leftAssoc _ = True
--Stateful actions processToken :: InToken -> RPNComp () processToken = \case
(InVal z) -> pushVal z (InOp op) -> pushOp op LParen -> pushParen RParen -> pushTillParen
pushTillParen :: RPNComp () pushTillParen = use _2 >>= \case
[] -> throwError "Unmatched right parenthesis" (s:st) -> case s of StOp o -> _1 %= (OutOp o:) >> _2 %= tail >> pushTillParen Paren -> _2 %= tail
pushOp :: Op -> RPNComp () pushOp o = use _2 >>= \case
[] -> _2 .= [StOp o] (s:st) -> case s of (StOp o2) -> if leftAssoc o && prec o == prec o2 || prec o < prec o2 then _1 %= (OutOp o2:) >> _2 %= tail >> pushOp o else _2 %= (StOp o:) Paren -> _2 %= (StOp o:)
pushVal :: Int -> RPNComp () pushVal n = _1 %= (OutVal n:)
pushParen :: RPNComp () pushParen = _2 %= (Paren:)
--Run StateT toRPN :: [InToken] -> Either String [OutToken] toRPN xs = evalStateT process ([],[])
where process = mapM_ processToken xs >> get >>= \(a,b) -> (reverse a++) <$> (mapM toOut b) toOut :: StackElem -> RPNComp OutToken toOut (StOp o) = return $ OutOp o toOut Paren = throwError "Unmatched left parenthesis"
--Parsing readTokens :: String -> Either String [InToken] readTokens = mapM f . words
where f = let g = return . InOp in \case { "^" -> g Pow; "*" -> g Mul; "/" -> g Div; "+" -> g Add; "-" -> g Sub; "(" -> return LParen; ")" -> return RParen; a -> case reads a of [] -> throwError $ "Invalid token `" ++ a ++ "`" [(_,x:[])] -> throwError $ "Invalid token `" ++ a ++ "`" [(v,[])] -> return $ InVal v }
--Showing showOutput (Left msg) = msg showOutput (Right xs) = unwords $ map show xs
main = do
a <- readline "Enter expression: " case a of Nothing -> putStrLn "Please enter a line" >> main Just "exit" -> return () Just l -> addHistory l >> case readTokens l of Left msg -> putStrLn msg >> main Right ts -> putStrLn (showOutput (toRPN ts)) >> main
</lang>
Enter expression: 3 + ( ( 4 + 5 ) Unmatched left parenthesis Enter expression: 3 + ( 4 + 5 ) ) Unmatched right parenthesis Enter expression: 3 + ( alan + 5 ) Invalid token `alan` Enter expression: 3 + ( 4 + 5 ) 3 4 5 + + Enter expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * 1 5 - 2 3 ^ ^ / +
Icon and Unicon
<lang Icon>procedure main()
infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" printf("Infix = %i\n",infix) printf("RPN = %i\n",Infix2RPN(infix))
end
link printf
record op_info(pr,as) # p=precedence, a=associativity (left=null)
procedure Infix2RPN(expr) #: Infix to RPN parser - shunting yard static oi initial {
oi := table() # precedence & associativity every oi[!"+-"] := op_info(2) # 2L every oi[!"*/"] := op_info(3) # 3L oi["^"] := op_info(4,1) # 4R } ostack := [] # operator stack rpn := "" # rpn pat := sprintf("%%5s : %%-%ds : %%s\n",*expr) # fmt printf(pat,"Token","Output","Op Stack") # header
expr ? until pos(0) do { # while tokens tab(many(' ')) # consume any seperator token := tab(upto(' ')|0) # get token printf(pat,token,rpn,list2string(ostack)) # report if token := numeric(token) then # ... numeric rpn ||:= token || " " else if member(oi,token) then { # ... operator while member(oi,op2 := ostack[1]) & ( /oi[token].as & oi[token].pr <= oi[op2].pr ) | ( \oi[token].as & oi[token].pr < oi[op2].pr ) do rpn ||:= pop(ostack) || " " push(ostack,token) } else # ... parenthesis if token == "(" then push(ostack,token) else if token == ")" then { until ostack[1] == "(" do rpn ||:= pop(ostack) || " " | stop("Unbalanced parenthesis") pop(ostack) # discard "(" } }
while token := pop(ostack) do # ... input exhausted if token == ("("|")") then stop("Unbalanced parenthesis") else { rpn ||:= token || " " printf(pat,"",rpn,list2string(ostack)) } return rpn
end
procedure list2string(L) #: format list as a string
every (s := "[ ") ||:= !L || " " return s || "]"
end</lang>
printf.icn provides formatting
Output:
Infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" Token : Output : Op Stack 3 : : [ ] + : 3 : [ ] 4 : 3 : [ + ] * : 3 4 : [ + ] 2 : 3 4 : [ * + ] / : 3 4 2 : [ * + ] ( : 3 4 2 * : [ / + ] 1 : 3 4 2 * : [ ( / + ] - : 3 4 2 * 1 : [ ( / + ] 5 : 3 4 2 * 1 : [ - ( / + ] ) : 3 4 2 * 1 5 : [ - ( / + ] ^ : 3 4 2 * 1 5 - : [ / + ] 2 : 3 4 2 * 1 5 - : [ ^ / + ] ^ : 3 4 2 * 1 5 - 2 : [ ^ / + ] 3 : 3 4 2 * 1 5 - 2 : [ ^ ^ / + ] : 3 4 2 * 1 5 - 2 3 ^ : [ ^ / + ] : 3 4 2 * 1 5 - 2 3 ^ ^ : [ / + ] : 3 4 2 * 1 5 - 2 3 ^ ^ / : [ + ] : 3 4 2 * 1 5 - 2 3 ^ ^ / + : [ ] RPN = "3 4 2 * 1 5 - 2 3 ^ ^ / + "
J
Code <lang J> NB. j does not have a verb based precedence. NB. j evaluates verb noun sequences from right to left. NB. Seriously. 18 precedence levels in C++ .
display=: ([: : (smoutput@:(, [: ; ' '&,&.>@:{:@:|:))) :: empty
Display=: adverb define
m display^:(0 -.@:-: x)y )
NB. Queue, Stack, Pop: m literal name of vector to use. verbose unless x is 0. NB. Implementation includes display, group push and pop not available in the RC FIFO & LIFO pages NB. As adverbs, these definitions work with any global variable. NB. Pop needs the feature, and it helps with display as well. Queue=: adverb define NB. enqueue y ('m'~)=: y ,~ (m~) EMPTY
x (m,' queue')Display y m Queue y )
Stack=: adverb define NB. Stack y ('m'~)=: (|.y) , (m~) EMPTY
x (m,' stack')Display y m Stack y )
Pop=: adverb define NB. Pop y items 0 m Pop y
y=. 0 {:@:, y NB. if y is empty use 0 instead rv=. y {. (m~) ('m'~)=: y }. (m~) x (m,' pop') Display rv rv )
NB. tests TEST=: 'TEST'Stack'abc' 'TEST'Stack'de' assert 'edc' -: 'TEST'Pop 3 assert 'ba' -: 'TEST'Pop 2 assert 0 (= #) TEST 'TEST'Queue'abc' 'TEST'Queue'de' assert 'ab' -: 'TEST'Pop 2 assert 'cde' -: 'TEST'Pop 3 assert 0 (= #) TEST
any=: +./
DIGITS=: a. {~ 48+i.10 NB. ASCII 48--57 precedence_oppression=: <;._1' +- */ ^ ( ) ',DIGITS associativity=: 'xLLRxxL'
classify=: {:@:I.@:(1 , any@e.&>)&precedence_oppression
NB. The required tokens are also tokens in j. NB. Use the default sequential machine ;: for lexical analysis. rclex=: (;~ classify)"0@:;:
NB. numbers can be treated as highest precedence operators
number=: Q Queue NB. put numbers onto the output queue
left=: S Stack NB. push left paren onto the stack
NB. Until the token at the top of the stack is (, pop NB. operators off the stack onto the output queue. NB. Pop the left parenthesis from the stack, but not onto the output queue. right=: 4 : 0 NB. If the token is a right parenthesis: i=. (S~) (i. rclex) '(' if. i (= #) S~ do.
smoutput'Check your parens!' throw.
end. x Q Queue x S Pop i x S Pop 1 EMPTY )
NB. If the token is an operator, o1, then: NB. NB. while there is an operator token, o2, at the top of the stack, and NB. either o1 is [[left-associative and its precedence is less than or NB. equal to that of o2]]"L*.<:", or o1 is [[right-associative and its precedence NB. is less than that of o2]]"R*.<", pop o2 off the stack, onto the output queue; NB. the tally of adjacent leading truths"NCT" NB. NB. push o1 onto the stack. o=: 4 : 0 P=. 0 0 {:: y L=. 'L' = P { associativity operators=. ({.~ i.&(rclex'(')) S~ NB. NCT L*.<: or R*.< i=. (+/@:(*./\)@:((L *. P&<:) +. ((-.L) *. P&<))@:(0&{::"1)) :: 0: operators x Q Queue x S Pop i x (S Stack) y EMPTY )
NB. terminating version of invalid invalid=: 4 : 0 smoutput 'invalid token ',0 1 {:: y throw. )
NB. demonstrated invalid invalid=: [: smoutput 'discarding invalid token ' , 0 1 {:: ]
NB. shunt_yard is a verb to implement shunt-yard parsing. NB. verbose defaults to 0. (quiet) NB. use: verbosity shunt_yard_parse algebraic_string shunt_yard_parse=: 0&$: : (4 : 0)
NB. j's data structure is array. Rank 1 arrays (vectors) NB. are just right for the stack and output queue.
'S Q'=: ;: 'OPERATOR OUTPUT' ('S'~)=:('Q'~)=: i.0 2
NB. Follow agenda for all tokens, result saved on global OUTPUT variable x (invalid`o`o`o`left`right`number@.(0 0 {:: ])"2 ,:"1@:rclex) y NB. x (invalid`o`o`o`left`right`o@.(0 0 {:: ])"2 ,:"1@:rclex) y NB. numbers can be treated as operators NB. check for junk on stack if. (rclex'(') e. S~ do.
smoutput'Check your other parens!' throw.
end.
NB. shift remaining operators onto the output queue x Q Queue x S Pop # S~
NB. return the output queue Q~ )
algebra_to_rpn=: {:@:|:@:shunt_yard_parse
fulfill_requirement=: ;@:(' '&,&.>)@:algebra_to_rpn </lang> Demonstration <lang J>
fulfill_requirement '3+4*2/(1-5)^2^3' 3 4 2 * 1 5 - 2 3 ^ ^ / +
shunt_yard_parse'3*)2+4)'
Check your parens!
shunt_yard_parse'3*(2+4'
Check your other parens!
algebra_to_rpn'1+x*(3+x)'
discarding invalid token x discarding invalid token x ┌─┬─┬─┬─┬─┐ │1│3│+│*│+│ └─┴─┴─┴─┴─┘
NB. Boxed form useful for evaluation algebra_to_rpn'0+666*(1+666*(2+666*(3)))' NB. polynomial evaluation.
┌─┬───┬─┬───┬─┬───┬─┬─┬─┬─┬─┬─┬─┐ │0│666│1│666│2│666│3│*│+│*│+│*│+│ └─┴───┴─┴───┴─┴───┴─┴─┴─┴─┴─┴─┴─┘
1 fulfill_requirement'3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
OUTPUT queue 3 OPERATOR pop OUTPUT queue OPERATOR stack + OUTPUT queue 4 OPERATOR pop OUTPUT queue OPERATOR stack * OUTPUT queue 2 OPERATOR pop * OUTPUT queue * OPERATOR stack / OPERATOR stack ( OUTPUT queue 1 OPERATOR pop OUTPUT queue OPERATOR stack - OUTPUT queue 5 OPERATOR pop - OUTPUT queue - OPERATOR pop ( OPERATOR pop OUTPUT queue OPERATOR stack ^ OUTPUT queue 2 OPERATOR pop OUTPUT queue OPERATOR stack ^ OUTPUT queue 3 OPERATOR pop ^ ^ / + OUTPUT queue ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
</lang>
Java
<lang java>import java.util.Stack;
public class ShuntingYard {
public static void main(String[] args) { String infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"; System.out.printf("infix: %s%n", infix); System.out.printf("postfix: %s%n", infixToPostfix(infix)); }
static String infixToPostfix(String infix) { final String ops = "-+/*^"; StringBuilder sb = new StringBuilder(); Stack<Integer> s = new Stack<>();
for (String token : infix.split("\\s")) { if (token.isEmpty()) continue; char c = token.charAt(0); int idx = ops.indexOf(c);
// check for operator if (idx != -1) { if (s.isEmpty()) s.push(idx); else { while (!s.isEmpty()) { int prec2 = s.peek() / 2; int prec1 = idx / 2; if (prec2 > prec1 || (prec2 == prec1 && c != '^')) sb.append(ops.charAt(s.pop())).append(' '); else break; } s.push(idx); } } else if (c == '(') { s.push(-2); // -2 stands for '(' } else if (c == ')') { // until '(' on stack, pop operators. while (s.peek() != -2) sb.append(ops.charAt(s.pop())).append(' '); s.pop(); } else { sb.append(token).append(' '); } } while (!s.isEmpty()) sb.append(ops.charAt(s.pop())).append(' '); return sb.toString(); }
}</lang>
Output:
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
JavaScript
<lang javascript>function Stack() {
this.dataStore = []; this.top = 0; this.push = push; this.pop = pop; this.peek = peek; this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function pop() {
return this.dataStore[--this.top];
}
function peek() {
return this.dataStore[this.top-1];
}
function length() {
return this.top;
}
var infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"; infix = infix.replace(/\s+/g, ); // remove spaces, so infix[i]!=" "
var s = new Stack(); var ops = "-+/*^"; var precedence = {"^":4, "*":3, "/":3, "+":2, "-":2}; var associativity = {"^":"Right", "*":"Left", "/":"Left", "+":"Left", "-":"Left"}; var token; var postfix = ""; var o1, o2;
for (var i = 0; i < infix.length; i++) {
token = infix[i]; if (token >= "0" && token <= "9") { // if token is operand (here limited to 0 <= x <= 9) postfix += token + " "; } else if (ops.indexOf(token) != -1) { // if token is an operator o1 = token; o2 = s.peek(); while (ops.indexOf(o2)!=-1 && ( // while operator token, o2, on top of the stack // and o1 is left-associative and its precedence is less than or equal to that of o2 (associativity[o1] == "Left" && (precedence[o1] <= precedence[o2]) ) || // the algorithm on wikipedia says: or o1 precedence < o2 precedence, but I think it should be // or o1 is right-associative and its precedence is less than that of o2 (associativity[o1] == "Right" && (precedence[o1] < precedence[o2])) )){ postfix += o2 + " "; // add o2 to output queue s.pop(); // pop o2 of the stack o2 = s.peek(); // next round } s.push(o1); // push o1 onto the stack } else if (token == "(") { // if token is left parenthesis s.push(token); // then push it onto the stack } else if (token == ")") { // if token is right parenthesis while (s.peek() != "("){ // until token at top is ( postfix += s.pop() + " "; } s.pop(); // pop (, but not onto the output queue }
} while (s.length()>0){
postfix += s.pop() + " ";
} print(postfix);</lang>
Output:
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Liberty BASIC
<lang lb> global stack$,queue$ stack$="" queue$=""
in$ = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" print "Input:" print in$
token$ = "#" print "No", "token", "stack", "queue"
while 1
i=i+1 token$ = word$(in$, i) if token$ = "" then i=i-1: exit while print i, token$, reverse$(stack$), queue$
select case case token$ = "(" call stack.push token$
case token$ = ")" while stack.peek$() <> "(" 'if stack is empty if stack$="" then print "Error: no matching '(' for token ";i: end call queue.push stack.pop$() wend discard$=stack.pop$() 'discard "("
case isOperator(token$) op1$=token$ while(isOperator(stack.peek$())) op2$=stack.peek$() select case case op2$<>"^" and precedence(op1$) = precedence(op2$) '"^" is the only right-associative operator call queue.push stack.pop$() case precedence(op1$) < precedence(op2$) call queue.push stack.pop$() case else exit while end select wend call stack.push op1$
case else 'number 'actually, wrong operator could end up here, like say % 'If the token is a number, then add it to the output queue. call queue.push token$ end select
wend
while stack$<>""
if stack.peek$() = "(" then print "no matching ')'": end call queue.push stack.pop$()
wend
print "Output:" while queue$<>""
print queue.pop$();" ";
wend print
end
'------------------------------------------ function isOperator(op$)
isOperator = instr("+-*/^", op$)<>0 AND len(op$)=1
end function
function precedence(op$)
if isOperator(op$) then precedence = 1 _ + (instr("+-*/^", op$)<>0) _ + (instr("*/^", op$)<>0) _ + (instr("^", op$)<>0) end if
end function
'------------------------------------------ sub stack.push s$
stack$=s$+"|"+stack$
end sub
sub queue.push s$
queue$=queue$+s$+"|"
end sub
function queue.pop$()
'it does return empty on empty stack or queue queue.pop$=word$(queue$,1,"|") queue$=mid$(queue$,instr(queue$,"|")+1)
end function
function stack.pop$()
'it does return empty on empty stack or queue stack.pop$=word$(stack$,1,"|") stack$=mid$(stack$,instr(stack$,"|")+1)
end function
function stack.peek$()
'it does return empty on empty stack or queue stack.peek$=word$(stack$,1,"|")
end function
function reverse$(s$)
reverse$ = "" token$="#" while token$<>"" i=i+1 token$=word$(s$,i,"|") reverse$ = token$;" ";reverse$ wend
end function </lang>
- Output:
Input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 No token stack queue 1 3 2 + 3| 3 4 + 3| 4 * + 3|4| 5 2 + * 3|4| 6 / + * 3|4|2| 7 ( + / 3|4|2|*| 8 1 + / ( 3|4|2|*| 9 - + / ( 3|4|2|*|1| 10 5 + / ( - 3|4|2|*|1| 11 ) + / ( - 3|4|2|*|1|5| 12 ^ + / 3|4|2|*|1|5|-| 13 2 + / ^ 3|4|2|*|1|5|-| 14 ^ + / ^ 3|4|2|*|1|5|-|2| 15 3 + / ^ ^ 3|4|2|*|1|5|-|2| Output: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Mathematica
<lang Mathematica>rpn[str_] :=
StringRiffle[ ToString /@ Module[{in = StringSplit[str], stack = {}, out = {}, next}, While[in != {}, next = in1; in = in2 ;;; Which[DigitQ[next], AppendTo[out, next], LetterQ[next], AppendTo[stack, next], next == ",", While[stack-1 != "(", AppendTo[out, stack-1]; stack = stack;; -2], next == "^", AppendTo[stack, "^"], next == "*", While[stack != {} && MatchQ[stack-1, "^" | "*" | "/"], AppendTo[out, stack-1]; stack = stack;; -2]; AppendTo[stack, "*"], next == "/", While[stack != {} && MatchQ[stack-1, "^" | "*" | "/"], AppendTo[out, stack-1]; stack = stack;; -2]; AppendTo[stack, "/"], next == "+", While[stack != {} && MatchQ[stack-1, "^" | "*" | "/" | "+" | "-"], AppendTo[out, stack-1]; stack = stack;; -2]; AppendTo[stack, "+"], next == "-", While[stack != {} && MatchQ[stack-1, "^" | "*" | "/" | "+" | "-"], AppendTo[out, stack-1]; stack = stack;; -2]; AppendTo[stack, "-"], next == "(", AppendTo[stack, "("], next == ")", While[stack-1 =!= "(", AppendTo[out, stack-1]; stack = stack;; -2]; stack = stack;; -2; If[StringQ[stack-1], AppendTo[out, stack-1]; stack = stack;; -2]]]; While[stack != {}, AppendTo[out, stack-1]; stack = stack;; -2]; out]];
Print[rpn["3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]];</lang>
- Output:
3 4 2 * 1 5 - / 2 3 ^ ^ +
Perl
<lang perl>my %prec = (
'^' => 4, '*' => 3, '/' => 3, '+' => 2, '-' => 2, '(' => 1
);
my %assoc = (
'^' => 'right', '*' => 'left', '/' => 'left', '+' => 'left', '-' => 'left'
);
sub shunting_yard {
my @inp = split ' ', $_[0]; my @ops; my @res;
my $report = sub { printf "%25s %-7s %10s %s\n", "@res", "@ops", $_[0], "@inp" }; my $shift = sub { $report->("shift @_"); push @ops, @_ }; my $reduce = sub { $report->("reduce @_"); push @res, @_ };
while (@inp) { my $token = shift @inp; if ( $token =~ /\d/ ) { $reduce->($token) } elsif ( $token eq '(' ) { $shift->($token) } elsif ( $token eq ')' ) { while ( @ops and "(" ne ( my $x = pop @ops ) ) { $reduce->($x) } } else { my $newprec = $prec{$token}; while (@ops) { my $oldprec = $prec{ $ops[-1] }; last if $newprec > $oldprec; last if $newprec == $oldprec and $assoc{$token} eq 'right'; $reduce->( pop @ops ); } $shift->($token); } } $reduce->( pop @ops ) while @ops; @res;
}
local $, = " "; print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'; </lang>
- Output:
reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 shift + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 + reduce 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 + shift * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 + * reduce 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 + reduce * ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + shift / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + / shift ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + / ( reduce 1 - 5 ) ^ 2 ^ 3 3 4 2 * 1 + / ( shift - 5 ) ^ 2 ^ 3 3 4 2 * 1 + / ( - reduce 5 ) ^ 2 ^ 3 3 4 2 * 1 5 + / ( reduce - ^ 2 ^ 3 3 4 2 * 1 5 - + / shift ^ 2 ^ 3 3 4 2 * 1 5 - + / ^ reduce 2 ^ 3 3 4 2 * 1 5 - 2 + / ^ shift ^ 3 3 4 2 * 1 5 - 2 + / ^ ^ reduce 3 3 4 2 * 1 5 - 2 3 + / ^ reduce ^ 3 4 2 * 1 5 - 2 3 ^ + / reduce ^ 3 4 2 * 1 5 - 2 3 ^ ^ + reduce / 3 4 2 * 1 5 - 2 3 ^ ^ / reduce + 3 4 2 * 1 5 - 2 3 ^ ^ / +
Perl 6
<lang perl6>my %prec =
'^' => 4, '*' => 3, '/' => 3, '+' => 2, '-' => 2, '(' => 1;
my %assoc =
'^' => 'right', '*' => 'left', '/' => 'left', '+' => 'left', '-' => 'left';
sub shunting-yard ($prog) {
my @inp = $prog.words; my @ops; my @res;
sub report($op) { printf "%25s %-7s %10s %s\n", ~@res, ~@ops, $op, ~@inp } sub shift($t) { report( "shift $t"); @ops.push: $t } sub reduce($t) { report("reduce $t"); @res.push: $t }
while @inp {
given @inp.shift { when /\d/ { reduce $_ }; when '(' { shift $_ } when ')' { while @ops and (my $x = @ops.pop and $x ne '(') { reduce $x } } default { my $newprec = %prec{$_}; while @ops { my $oldprec = %prec{@ops[*-1]}; last if $newprec > $oldprec; last if $newprec == $oldprec and %assoc{$_} eq 'right'; reduce @ops.pop; } shift $_; } }
} reduce @ops.pop while @ops; @res;
}
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';</lang>
- Output:
reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 shift + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 + reduce 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 + shift * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 + * reduce 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 + reduce * ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + shift / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + / shift ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + / ( reduce 1 - 5 ) ^ 2 ^ 3 3 4 2 * 1 + / ( shift - 5 ) ^ 2 ^ 3 3 4 2 * 1 + / ( - reduce 5 ) ^ 2 ^ 3 3 4 2 * 1 5 + / ( reduce - ^ 2 ^ 3 3 4 2 * 1 5 - + / shift ^ 2 ^ 3 3 4 2 * 1 5 - + / ^ reduce 2 ^ 3 3 4 2 * 1 5 - 2 + / ^ shift ^ 3 3 4 2 * 1 5 - 2 + / ^ ^ reduce 3 3 4 2 * 1 5 - 2 3 + / ^ reduce ^ 3 4 2 * 1 5 - 2 3 ^ + / reduce ^ 3 4 2 * 1 5 - 2 3 ^ ^ + reduce / 3 4 2 * 1 5 - 2 3 ^ ^ / reduce + 3 4 2 * 1 5 - 2 3 ^ ^ / +
PicoLisp
Note: "^" is a meta-character and must be escaped in strings <lang PicoLisp>(de operator (Op)
(member Op '("\^" "*" "/" "+" "-")) )
(de leftAssoc (Op)
(member Op '("*" "/" "+" "-")) )
(de precedence (Op)
(case Op ("\^" 4) (("*" "/") 3) (("+" "-") 2) ) )
(de shuntingYard (Str)
(make (let (Fmt (-7 -30 -4) Stack) (tab Fmt "Token" "Output" "Stack") (for Token (str Str "_") (cond ((num? Token) (link @)) ((= "(" Token) (push 'Stack Token)) ((= ")" Token) (until (= "(" (car Stack)) (unless Stack (quit "Unbalanced Stack") ) (link (pop 'Stack)) ) (pop 'Stack) ) (T (while (and (operator (car Stack)) ((if (leftAssoc (car Stack)) <= <) (precedence Token) (precedence (car Stack)) ) ) (link (pop 'Stack)) ) (push 'Stack Token) ) ) (tab Fmt Token (glue " " (made)) Stack) ) (while Stack (when (= "(" (car Stack)) (quit "Unbalanced Stack") ) (link (pop 'Stack)) (tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</lang>
Output: <lang PicoLisp>: (shuntingYard "3 + 4 * 2 / (1 - 5) \^ 2 \^ 3") Token Output Stack 3 3 + 3 + 4 3 4 +
- 3 4 *+
2 3 4 2 *+ / 3 4 2 * /+ ( 3 4 2 * (/+ 1 3 4 2 * 1 (/+ - 3 4 2 * 1 -(/+ 5 3 4 2 * 1 5 -(/+ ) 3 4 2 * 1 5 - /+ ^ 3 4 2 * 1 5 - ^/+ 2 3 4 2 * 1 5 - 2 ^/+ ^ 3 4 2 * 1 5 - 2 ^^/+ 3 3 4 2 * 1 5 - 2 3 ^^/+
3 4 2 * 1 5 - 2 3 ^ ^/+ 3 4 2 * 1 5 - 2 3 ^ ^ /+ 3 4 2 * 1 5 - 2 3 ^ ^ / + 3 4 2 * 1 5 - 2 3 ^ ^ / +
-> (3 4 2 "*" 1 5 "-" 2 3 "\^" "\^" "/" "+")</lang>
PL/I
<lang PL/I> cvt: procedure options (main); /* 15 January 2012. */
declare (in, stack, out) character (100) varying; declare (ch, chs) character (1); declare display bit (1) static initial ('0'b);
in = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
in = '(' || in || ' ) '; /* Initialize with parentheses */
put skip edit ('INPUT', 'STACK', 'OUTPUT') (a, col(37), a, col(47), a);
stack = ' '; out = ; /* Initialize */ do while (length (in) > 0); ch = substr(in, 1, 1); select (ch); when (' ') ;
when ('+', '-', '*', '/', '^') do; /* Copy any equal or higher-priority operators from the stack */ /* to the output string */ chs = substr(stack, 1, 1); do while ((spriority(chs) >= priority(ch)) & ( chs ^= ')' ) ); if display then put skip list ('unstacking: ' || chs); out = out || ' ' || chs; stack = substr(stack, 2); chs = substr(stack, 1, 1); end; /* Now copy the input to the TOS. */ if display then put skip list ('copying ' || ch || ' to TOS'); stack = ch || stack; end; when ( '(' ) do; stack = '(' || stack; if display then put skip list ('stacking the (' ); end; when ( ')' ) do; /* copy all operators from the stack to the output, */ /* until a '(' is encountered. */ chs = substr(stack, 1, 1); do while (chs ^= '(' ); if display then put skip list ('copying stack ' || chs || ' to output'); put skip edit (stack, out) (col(37), a, col(47), a); out = out || ' ' || chs; stack = substr(stack, 2); chs = substr(stack, 1, 1); end; /* Now delete the '(' from the input and */ /* the ')' from the top of the stack. */ if display then put skip edit ('Deleting ( from TOS') (col(30), a); stack = substr(stack, 2); /* The '(' on the input is removed at the end of the loop. */ end; otherwise /* it's an operand. */ do; out = out || ' '; do while (ch ^= ' '); if display then put skip list ('copying ' || ch || ' to output'); out = out || ch; in = substr(in, 2); ch = substr(in, 1, 1); end; end; end; in = substr(in, 2); /* Remove one character from the input */ put skip edit (in, stack, out) (a, col(37), a, col(47), a); end;
priority: procedure (ch) returns (character(1));
declare ch character (1);
return ( translate(ch, '1122335', '()+-*/^' ) );
end priority;
spriority: procedure (ch) returns (character(1));
declare ch character (1);
return ( translate(ch, '1122334', '()+-*/^' ) );
end spriority;
end cvt; </lang> Output: <lang> INPUT STACK OUTPUT 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) ( + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) ( 3
4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) +( 3
4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) +( 3
- 2 / ( 1 - 5 ) ^ 2 ^ 3 ) +( 3 4
2 / ( 1 - 5 ) ^ 2 ^ 3 ) *+( 3 4
2 / ( 1 - 5 ) ^ 2 ^ 3 ) *+( 3 4 / ( 1 - 5 ) ^ 2 ^ 3 ) *+( 3 4 2
( 1 - 5 ) ^ 2 ^ 3 ) /+( 3 4 2 *
( 1 - 5 ) ^ 2 ^ 3 ) /+( 3 4 2 *
1 - 5 ) ^ 2 ^ 3 ) (/+( 3 4 2 *
1 - 5 ) ^ 2 ^ 3 ) (/+( 3 4 2 * - 5 ) ^ 2 ^ 3 ) (/+( 3 4 2 * 1
5 ) ^ 2 ^ 3 ) -(/+( 3 4 2 * 1
5 ) ^ 2 ^ 3 ) -(/+( 3 4 2 * 1 ) ^ 2 ^ 3 ) -(/+( 3 4 2 * 1 5
-(/+( 3 4 2 * 1 5 ^ 2 ^ 3 ) /+( 3 4 2 * 1 5 -
^ 2 ^ 3 ) /+( 3 4 2 * 1 5 -
2 ^ 3 ) ^/+( 3 4 2 * 1 5 -
2 ^ 3 ) ^/+( 3 4 2 * 1 5 - ^ 3 ) ^/+( 3 4 2 * 1 5 - 2
3 ) ^^/+( 3 4 2 * 1 5 - 2
3 ) ^^/+( 3 4 2 * 1 5 - 2 ) ^^/+( 3 4 2 * 1 5 - 2 3
^^/+( 3 4 2 * 1 5 - 2 3 ^/+( 3 4 2 * 1 5 - 2 3 ^ /+( 3 4 2 * 1 5 - 2 3 ^ ^ +( 3 4 2 * 1 5 - 2 3 ^ ^ / 3 4 2 * 1 5 - 2 3 ^ ^ / + 3 4 2 * 1 5 - 2 3 ^ ^ / +
</lang>
Python
Parenthesis are added to the operator table then special-cased in the code. This solution includes the extra credit. <lang python>from collections import namedtuple from pprint import pprint as pp
OpInfo = namedtuple('OpInfo', 'prec assoc') L, R = 'Left Right'.split()
ops = {
'^': OpInfo(prec=4, assoc=R), '*': OpInfo(prec=3, assoc=L), '/': OpInfo(prec=3, assoc=L), '+': OpInfo(prec=2, assoc=L), '-': OpInfo(prec=2, assoc=L), '(': OpInfo(prec=9, assoc=L), ')': OpInfo(prec=0, assoc=L), }
NUM, LPAREN, RPAREN = 'NUMBER ( )'.split()
def get_input(inp = None):
'Inputs an expression and returns list of (TOKENTYPE, tokenvalue)' if inp is None: inp = input('expression: ') tokens = inp.strip().split() tokenvals = [] for token in tokens: if token in ops: tokenvals.append((token, ops[token])) #elif token in (LPAREN, RPAREN): # tokenvals.append((token, token)) else: tokenvals.append((NUM, token)) return tokenvals
def shunting(tokenvals):
outq, stack = [], [] table = ['TOKEN,ACTION,RPN OUTPUT,OP STACK,NOTES'.split(',')] for token, val in tokenvals: note = action = if token is NUM: action = 'Add number to output' outq.append(val) table.append( (val, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) ) elif token in ops: t1, (p1, a1) = token, val v = t1 note = 'Pop ops from stack to output' while stack: t2, (p2, a2) = stack[-1] if (a1 == L and p1 <= p2) or (a1 == R and p1 < p2): if t1 != RPAREN: if t2 != LPAREN: stack.pop() action = '(Pop op)' outq.append(t2) else: break else: if t2 != LPAREN: stack.pop() action = '(Pop op)' outq.append(t2) else: stack.pop() action = '(Pop & discard "(")' table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) ) break table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) ) v = note = else: note = break note = note = if t1 != RPAREN: stack.append((token, val)) action = 'Push op token to stack' else: action = 'Discard ")"' table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) ) note = 'Drain stack to output' while stack: v = t2, (p2, a2) = stack[-1] action = '(Pop op)' stack.pop() outq.append(t2) table.append( (v, action, ' '.join(outq), ' '.join(s[0] for s in stack), note) ) v = note = return table
if __name__ == '__main__':
infix = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' print( 'For infix expression: %r\n' % infix ) rp = shunting(get_input(infix)) maxcolwidths = [len(max(x, key=len)) for x in zip(*rp)] row = rp[0] print( ' '.join('{cell:^{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row))) for row in rp[1:]: print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
print('\n The final output RPN is: %r' % rp[-1][2])</lang>
- Sample output
For infix expression: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' TOKEN ACTION RPN OUTPUT OP STACK NOTES 3 Add number to output 3 + Push op token to stack 3 + 4 Add number to output 3 4 + * Push op token to stack 3 4 + * 2 Add number to output 3 4 2 + * / (Pop op) 3 4 2 * + Pop ops from stack to output Push op token to stack 3 4 2 * + / ( Push op token to stack 3 4 2 * + / ( 1 Add number to output 3 4 2 * 1 + / ( - Push op token to stack 3 4 2 * 1 + / ( - 5 Add number to output 3 4 2 * 1 5 + / ( - ) (Pop op) 3 4 2 * 1 5 - + / ( Pop ops from stack to output (Pop & discard "(") 3 4 2 * 1 5 - + / Discard ")" 3 4 2 * 1 5 - + / ^ Push op token to stack 3 4 2 * 1 5 - + / ^ 2 Add number to output 3 4 2 * 1 5 - 2 + / ^ ^ Push op token to stack 3 4 2 * 1 5 - 2 + / ^ ^ 3 Add number to output 3 4 2 * 1 5 - 2 3 + / ^ ^ (Pop op) 3 4 2 * 1 5 - 2 3 ^ + / ^ Drain stack to output (Pop op) 3 4 2 * 1 5 - 2 3 ^ ^ + / (Pop op) 3 4 2 * 1 5 - 2 3 ^ ^ / + (Pop op) 3 4 2 * 1 5 - 2 3 ^ ^ / + The final output RPN is: '3 4 2 * 1 5 - 2 3 ^ ^ / +'
Racket
<lang Racket>
- lang racket
- print column of width w
(define (display-col w s)
(let* ([n-spaces (- w (string-length s))] [spaces (make-string n-spaces #\space)]) (display (string-append s spaces))))
- print columns given widths (idea borrowed from PicoLisp)
(define (tab ws . ss) (for-each display-col ws ss) (newline))
(define input "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")
(define (paren? s) (or (string=? s "(") (string=? s ")"))) (define-values (prec lasso? rasso? op?)
(let ([table '(["^" 4 r] ["*" 3 l] ["/" 3 l] ["+" 2 l] ["-" 2 l])]) (define (asso x) (caddr (assoc x table))) (values (λ (x) (cadr (assoc x table))) (λ (x) (symbol=? (asso x) 'l)) (λ (x) (symbol=? (asso x) 'r)) (λ (x) (member x (map car table))))))
(define (shunt s)
(define widths (list 8 (string-length input) (string-length input) 20)) (tab widths "TOKEN" "OUT" "STACK" "ACTION") (let shunt ([out '()] [ops '()] [in (string-split s)] [action ""]) (match in ['() (if (memf paren? ops) (error "unmatched parens") (reverse (append (reverse ops) out)))] [(cons x in) (tab widths x (string-join (reverse out) " ") (string-append* ops) action) (match x [(? string->number n) (shunt (cons n out) ops in (format "out ~a" n))] ["(" (shunt out (cons "(" ops) in "push (")] [")" (let-values ([(l r) (splitf-at ops (λ (y) (not (string=? y "("))))]) (match r ['() (error "unmatched parens")] [(cons _ r) (shunt (append (reverse l) out) r in "clear til )")]))] [else (let-values ([(l r) (splitf-at ops (λ (y) (and (op? y) ((if (lasso? x) <= <) (prec x) (prec y)))))]) (shunt (append (reverse l) out) (cons x r) in (format "out ~a, push ~a" l x)))])])))
</lang>
- Output:
> (shunt input) TOKEN OUT STACK ACTION 3 + 3 out 3 4 3 + out (), push + * 3 4 + out 4 2 3 4 *+ out (), push * / 3 4 2 *+ out 2 ( 3 4 2 * /+ out (*), push / 1 3 4 2 * (/+ push ( - 3 4 2 * 1 (/+ out 1 5 3 4 2 * 1 -(/+ out (), push - ) 3 4 2 * 1 5 -(/+ out 5 ^ 3 4 2 * 1 5 - /+ clear til ) 2 3 4 2 * 1 5 - ^/+ out (), push ^ ^ 3 4 2 * 1 5 - 2 ^/+ out 2 3 3 4 2 * 1 5 - 2 ^^/+ out (), push ^ '("3" "4" "2" "*" "1" "5" "-" "2" "3" "^" "^" "/" "+")
REXX
These REXX versions below allow multi-character tokens (both operands and operators).
assume expression is correct
<lang rexx>/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/ parse arg x /*obtain optional argument from the CL.*/ if x= then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ ox=x x='(' space(x) ") " /*force stacking for the expression. */
- =words(x) /*get number of tokens in expression. */
do i=1 for #; @.i=word(x, i) /*assign the input tokens to an array. */ end /*i*/
tell=1 /*set to 0 if working steps not wanted.*/ L=max( 20, length(x) ) /*use twenty for the minimum show width*/
say 'token' center("input" , L, '─') center("stack" , L%2, '─'),
center("output", L, '─') center("action", L, '─')
op= ")(-+/*^"; Rop=substr(op,3); p.=; n=length(op); RPN= /*some handy-dandy vars.*/ s.=
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/
$= /* [↑] assign the operator priorities.*/
do k=1 for #; ?=@.k /*process each token from the @. list.*/ select /*@.k is: (, operator, ), operand*/ when ?=='(' then do; $="(" $; call show 'moving' ? "──► stack"; end when isOp(?) then do; !=word($, 1) /*get token from stack*/ do while ! \==')' & s.!>=p.? RPN=RPN ! /*add token to RPN.*/ $=subword($, 2) /*del token from stack*/ call show 'unstacking:' ! !=word($, 1) /*get token from stack*/ end /*while*/ $=? $ /*add token to stack*/ call show 'moving' ? "──► stack" end when ?==')' then do; !=word($, 1) /*get token from stack*/ do while !\=='('; RPN=RPN ! /*add token to RPN. */ $=subword($, 2) /*del token from stack*/ != word($, 1) /*get token from stack*/ call show 'moving stack' ! "──► RPN" end /*while*/ $=subword($, 2) /*del token from stack*/ call show 'deleting ( from the stack' end otherwise RPN=RPN ? /*add operand to RPN. */ call show 'moving' ? "──► RPN" end /*select*/ end /*k*/
say RPN=space(RPN $) /*elide any superfluous blanks in RPN. */ say ' input:' ox; say " RPN──►" RPN /*display the input and the RPN. */ parse source upper . y . /*invoked via the C.L. or REXX pgm? */ if y=='COMMAND' then exit /*stick a fork in it, we're all done. */
else return RPN /*return RPN to invoker (the RESULT). */
/*──────────────────────────────────────────────────────────────────────────────────────────*/ isOp: return pos(arg(1),rOp) \== 0 /*is the first argument a "real" operator? */ show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</lang> output when using the default input:
token ──────────────input─────────────── ──────stack────── ──────────────output────────────── ──────────────action────────────── ( ( 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) ( moving ( ──► stack 3 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) ( 3 moving 3 ──► RPN + + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) + ( 3 moving + ──► stack 4 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) + ( 3 4 moving 4 ──► RPN * * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) * + ( 3 4 moving * ──► stack 2 2 / ( 1 - 5 ) ^ 2 ^ 3 ) * + ( 3 4 2 moving 2 ──► RPN / / ( 1 - 5 ) ^ 2 ^ 3 ) + ( 3 4 2 * unstacking: * / / ( 1 - 5 ) ^ 2 ^ 3 ) / + ( 3 4 2 * moving / ──► stack ( ( 1 - 5 ) ^ 2 ^ 3 ) ( / + ( 3 4 2 * moving ( ──► stack 1 1 - 5 ) ^ 2 ^ 3 ) ( / + ( 3 4 2 * 1 moving 1 ──► RPN - - 5 ) ^ 2 ^ 3 ) - ( / + ( 3 4 2 * 1 moving - ──► stack 5 5 ) ^ 2 ^ 3 ) - ( / + ( 3 4 2 * 1 5 moving 5 ──► RPN ) ) ^ 2 ^ 3 ) ( / + ( 3 4 2 * 1 5 - moving stack ( ──► RPN ) ) ^ 2 ^ 3 ) / + ( 3 4 2 * 1 5 - deleting ( from the stack ^ ^ 2 ^ 3 ) ^ / + ( 3 4 2 * 1 5 - moving ^ ──► stack 2 2 ^ 3 ) ^ / + ( 3 4 2 * 1 5 - 2 moving 2 ──► RPN ^ ^ 3 ) ^ ^ / + ( 3 4 2 * 1 5 - 2 moving ^ ──► stack 3 3 ) ^ ^ / + ( 3 4 2 * 1 5 - 2 3 moving 3 ──► RPN ) ) ^ / + ( 3 4 2 * 1 5 - 2 3 ^ moving stack ^ ──► RPN ) ) / + ( 3 4 2 * 1 5 - 2 3 ^ ^ moving stack / ──► RPN ) ) + ( 3 4 2 * 1 5 - 2 3 ^ ^ / moving stack + ──► RPN ) ) ( 3 4 2 * 1 5 - 2 3 ^ ^ / + moving stack ( ──► RPN ) ) 3 4 2 * 1 5 - 2 3 ^ ^ / + deleting ( from the stack input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 RPN──► 3 4 2 * 1 5 - 2 3 ^ ^ / +
checks expression for balanced ()
Since these REXX versions of infix to RPN conversion affixes a leading ( and trailing ) to the expression, an
invalid expression such as ) ( would be made legal by the aforemention affixing: ) (
gets transformed into ( ) ( )
Therefore, code was added to check for this condition, and also checks for mismatched parenthesis.
The select group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source. <lang rexx>/*REXX pgm converts infix arith. expressions to Reverse Polish notation (shunting─yard).*/ parse arg x /*obtain optional argument from the CL.*/ if x= then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/ g=0 /* G is a counter of ( and ) */
do p=1 for words(x); _=word(x,p) /*catches unbalanced ( ) and ) ( */ if _=='(' then g=g+1 else if _==')' then do; g=g-1; if g<0 then g=-1e8; end end /*p*/
ox=x x='(' space(x) ") " /*force stacking for the expression. */
- =words(x) /*get number of tokens in expression. */
good= (g==0) /*indicate expression is good or bad.*/
do i=1 for #; @.i=word(x, i) /*assign the input tokens to an array. */ end /*i*/
tell=1 /*set to 0 if working steps not wanted.*/ L=max( 20, length(x) ) /*use twenty for the minimum show width*/ if good then say 'token' center("input" , L, '─') center("stack" , L%2, '─'),
center("output", L, '─') center("action", L, '─')
op= ")(-+/*^"; Rop=substr(op,3); p.=; n=length(op); RPN= /*some handy-dandy vars.*/ s.=
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/
$= /* [↑] assign the operator priorities.*/
do k=1 for #*good; ?=@.k /*process each token from the @. list.*/ select /*@.k is: ( operator ) operand.*/ when ?=='(' then do; $="(" $; call show 'moving' ? "──► stack"; end when isOp(?) then do; !=word($, 1) /*get token from stack*/ do while ! \==')' & s.!>=p.? RPN=RPN ! /*add token to RPN.*/ $=subword($, 2) /*del token from stack*/ call show 'unstacking:' ! !=word($, 1) /*get token from stack*/ end /*while*/ $=? $ /*add token to stack*/ call show 'moving' ? "──► stack" end when ?==')' then do; !=word($, 1) /*get token from stack*/ do while !\=='('; RPN=RPN ! /*add token to RPN.*/ $=subword($, 2) /*del token from stack*/ != word($, 1) /*get token from stack*/ call show 'moving stack' ! "──► RPN" end /*while*/ $=subword($, 2) /*del token from stack*/ call show 'deleting ( from the stack' end otherwise RPN=RPN ? /*add operand to RPN.*/ call show 'moving' ? "──► RPN" end /*select*/ end /*k*/
say RPN=space(RPN $); if \good then RPN= '─────── error in expression ───────' /*error? */ say ' input:' ox; say " RPN──►" RPN /*display the input and the RPN. */ parse source upper . y . /*invoked via the C.L. or REXX pgm? */ if y=='COMMAND' then exit /*stick a fork in it, we're all done. */
else return RPN /*return RPN to invoker (the RESULT). */
/*──────────────────────────────────────────────────────────────────────────────────────────*/ isOp: return pos(arg(1), Rop) \== 0 /*is the first argument a "real" operator? */ show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</lang> output when using the input: ) (
input: ) ( RPN──► ─────── error in expression ───────
Ruby
See Parsing/RPN/Ruby
<lang ruby>rpn = RPNExpression.from_infix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")</lang> outputs
for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Term Action Output Stack 3 PUSH V ["3"] [] + PUSH OP ["3"] ["+"] 4 PUSH V ["3", "4"] ["+"] * PUSH OP ["3", "4"] ["+", "*"] 2 PUSH V ["3", "4", "2"] ["+", "*"] / MUL ["3", "4", "2", "*"] ["+"] * has higher precedence than / / PUSH OP ["3", "4", "2", "*"] ["+", "/"] ( OPEN_P ["3", "4", "2", "*"] ["+", "/", "("] 1 PUSH V ["3", "4", "2", "*", "1"] ["+", "/", "("] - PUSH OP ["3", "4", "2", "*", "1"] ["+", "/", "(", "-"] 5 PUSH V ["3", "4", "2", "*", "1", "5"] ["+", "/", "(", "-"] ) SUB ["3", "4", "2", "*", "1", "5", "-"] ["+", "/", "("] unwinding parenthesis ) CLOSE_P ["3", "4", "2", "*", "1", "5", "-"] ["+", "/"] ^ PUSH OP ["3", "4", "2", "*", "1", "5", "-"] ["+", "/", "^"] 2 PUSH V ["3", "4", "2", "*", "1", "5", "-", "2"] ["+", "/", "^"] ^ PUSH OP ["3", "4", "2", "*", "1", "5", "-", "2"] ["+", "/", "^", "^"] 3 PUSH V ["3", "4", "2", "*", "1", "5", "-", "2", "3"] ["+", "/", "^", "^"] RPN = 3 4 2 * 1 5 - 2 3 ^ ^ / +
Sidef
<lang ruby>var prec = Hash(
'^' => 4, '*' => 3, '/' => 3, '+' => 2, '-' => 2, '(' => 1,
);
var assoc = Hash(
'^' => 'right', '*' => 'left', '/' => 'left', '+' => 'left', '-' => 'left',
);
func shunting_yard(prog) {
var inp = prog.words; var ops = []; var res = [];
func report (op) { printf("%25s %-7s %10s %s\n", res.join(' '), ops.join(' '), op, inp.join(' ')) } func shift (t) { report( "shift #{t}"); ops << t } func reduce (t) { report("reduce #{t}"); res << t }
while (inp) { given(var t = inp.shift) { when (/\d/) { reduce(t) } when ('(') { shift(t) } when (')') { var x; while (ops && (x = ops.pop) && (x != '(')) { reduce(x) } } default { var newprec = prec{t}; while (ops) { var oldprec = prec{ops[-1]};
break if (newprec > oldprec) break if ((newprec == oldprec) && (assoc{t} == 'right'))
reduce(ops.pop); } shift(t); } } } while (ops) { reduce(ops.pop) } return res
}
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ');</lang>
- Output:
reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 shift + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 + reduce 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 + shift * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 + * reduce 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 + reduce * ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + shift / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + / shift ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * + / ( reduce 1 - 5 ) ^ 2 ^ 3 3 4 2 * 1 + / ( shift - 5 ) ^ 2 ^ 3 3 4 2 * 1 + / ( - reduce 5 ) ^ 2 ^ 3 3 4 2 * 1 5 + / ( reduce - ^ 2 ^ 3 3 4 2 * 1 5 - + / shift ^ 2 ^ 3 3 4 2 * 1 5 - + / ^ reduce 2 ^ 3 3 4 2 * 1 5 - 2 + / ^ shift ^ 3 3 4 2 * 1 5 - 2 + / ^ ^ reduce 3 3 4 2 * 1 5 - 2 3 + / ^ reduce ^ 3 4 2 * 1 5 - 2 3 ^ + / reduce ^ 3 4 2 * 1 5 - 2 3 ^ ^ + reduce / 3 4 2 * 1 5 - 2 3 ^ ^ / reduce + 3 4 2 * 1 5 - 2 3 ^ ^ / +
Swift
<lang Swift>import Foundation
// Using arrays for both stack and queue struct Stack<T> {
private(set) var elements = [T]() var isEmpty: Bool { return elements.isEmpty }
mutating func push(newElement: T) { elements.append(newElement) }
mutating func pop() -> T { return elements.removeLast() }
func top() -> T? { return elements.last }
}
struct Queue<T> {
private(set) var elements = [T]() var isEmpty: Bool { return elements.isEmpty }
mutating func enqueue(newElement: T) { elements.append(newElement) }
mutating func dequeue() -> T { return elements.removeFirst() }
}
enum Associativity { case Left, Right }
// Define abstract interface, which can be used to restrict Set extension protocol OperatorType: Comparable, Hashable {
var name: String { get } var precedence: Int { get } var associativity: Associativity { get }
}
struct Operator: OperatorType {
let name: String let precedence: Int let associativity: Associativity // same operator names are not allowed var hashValue: Int { return "\(name)".hashValue }
init(_ name: String, _ precedence: Int, _ associativity: Associativity) { self.name = name; self.precedence = precedence; self.associativity = associativity }
}
func ==(x: Operator, y: Operator) -> Bool {
// same operator names are not allowed return x.name == y.name
}
func <(x: Operator, y: Operator) -> Bool {
// compare operators by their precedence and associavity return (x.associativity == .Left && x.precedence == y.precedence) || x.precedence < y.precedence
}
extension Set where Element: OperatorType {
func contains(op: String?) -> Bool { guard let operatorName = op else { return false } return contains { $0.name == operatorName } }
subscript (operatorName: String) -> Element? { get { return filter { $0.name == operatorName }.first } }
}
// Convenience extension String {
var isNumber: Bool { return Double(self) != nil }
}
struct ShuntingYard {
enum Error: ErrorType { case MismatchedParenthesis(String) case UnrecognizedToken(String) }
static func parse(input: String, operators: Set<Operator>) throws -> String { var stack = Stack<String>() var output = Queue<String>() let tokens = input.componentsSeparatedByString(" ")
for token in tokens { // Wikipedia: if token is a number add it to the output queue if token.isNumber { output.enqueue(token) } // Wikipedia: else if token is a operator: else if operators.contains(token) { // Wikipedia: while there is a operator on top of the stack and has lower precedence than current operator (token) while operators.contains(stack.top()) && hasLowerPrecedence(token, stack.top()!, operators) { // Wikipedia: pop it off to the output queue output.enqueue(stack.pop()) } // Wikipedia: push current operator (token) onto the operator stack stack.push(token) } // Wikipedia: If the token is a left parenthesis, then push it onto the stack. else if token == "(" { stack.push(token) } // Wikipedia: If the token is a right parenthesis: else if token == ")" { // Wikipedia: Until the token at the top of the stack is a left parenthesis while !stack.isEmpty && stack.top() != "(" { // Wikipedia: pop operators off the stack onto the output queue. output.enqueue(stack.pop()) }
// If the stack runs out, than there are mismatched parentheses. if stack.isEmpty { throw Error.MismatchedParenthesis(input) }
// Wikipedia: Pop the left parenthesis from the stack, but not onto the output queue. stack.pop() } // if token is not number, operator or a parenthesis, then is not recognized else { throw Error.UnrecognizedToken(token) } }
// Wikipedia: When there are no more tokens to read:
// Wikipedia: While there are still operator tokens in the stack: while operators.contains(stack.top()) { // Wikipedia: Pop the operator onto the output queue. output.enqueue(stack.pop()) }
// Wikipedia: If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses // Note: Assume that all operators has been poped onto the output queue. if stack.isEmpty == false { throw Error.MismatchedParenthesis(input) }
return output.elements.joinWithSeparator(" ") }
static private func containsOperator(stack: Stack<String>, _ operators: [String: NSDictionary]) -> Bool { guard stack.isEmpty == false else { return false } // Is there a matching operator in the operators set? return operators[stack.top()!] != nil ? true : false }
static private func hasLowerPrecedence(x: String, _ y: String, _ operators: Set<Operator>) -> Bool { guard let first = operators[x], let second = operators[y] else { return false } return first < second }
}
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" let operators: Set<Operator> = [
Operator("^", 4, .Right), Operator("*", 3, .Left), Operator("/", 3, .Left), Operator("+", 2, .Left), Operator("-", 2, .Left)
] let output = try! ShuntingYard.parse(input, operators: operators)
print("input: \(input)") print("output: \(output)") </lang>
- Output:
input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 output: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Tcl
<lang tcl>package require Tcl 8.5
- Helpers
proc tokenize {str} {
regexp -all -inline {[\d.]+|[-*^+/()]} $str
} proc precedence op {
dict get {^ 4 * 3 / 3 + 2 - 2} $op
} proc associativity op {
if {$op eq "^"} {return "right"} else {return "left"}
}
proc shunting {expression} {
set stack {} foreach token [tokenize $expression] {
if {[string is double $token]} { puts "add to output: $token" lappend output $token } elseif {$token eq "("} { puts "push parenthesis" lappend stack $token } elseif {$token eq ")"} { puts "popping to parenthesis" while {[lindex $stack end] ne "("} { lappend output [lindex $stack end] set stack [lreplace $stack end end] puts "...popped [lindex $output end] to output" } set stack [lreplace $stack end end] puts "...found parenthesis" } else { puts "adding operator: $token" set p [precedence $token] set a [associativity $token] while {[llength $stack]} { set o2 [lindex $stack end] if { $o2 ne "(" && (($a eq "left" && $p <= [precedence $o2]) || ($a eq "right" && $p < [precedence $o2])) } then { puts "...popped operator $o2 to output" lappend output $o2 set stack [lreplace $stack end end] } else { break } } lappend stack $token } puts "\t\tOutput:\t$output\n\t\tStack:\t$stack"
} puts "transferring tokens from stack to output" lappend output {*}[lreverse $stack]
}
puts [shunting "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]</lang> Output:
add to output: 3 Output: 3 Stack: adding operator: + Output: 3 Stack: + add to output: 4 Output: 3 4 Stack: + adding operator: * Output: 3 4 Stack: + * add to output: 2 Output: 3 4 2 Stack: + * adding operator: / ...popped operator * to output Output: 3 4 2 * Stack: + / push parenthesis Output: 3 4 2 * Stack: + / ( add to output: 1 Output: 3 4 2 * 1 Stack: + / ( adding operator: - Output: 3 4 2 * 1 Stack: + / ( - add to output: 5 Output: 3 4 2 * 1 5 Stack: + / ( - popping to parenthesis ...popped - to output ...found parenthesis Output: 3 4 2 * 1 5 - Stack: + / adding operator: ^ Output: 3 4 2 * 1 5 - Stack: + / ^ add to output: 2 Output: 3 4 2 * 1 5 - 2 Stack: + / ^ adding operator: ^ Output: 3 4 2 * 1 5 - 2 Stack: + / ^ ^ add to output: 3 Output: 3 4 2 * 1 5 - 2 3 Stack: + / ^ ^ transferring tokens from stack to output 3 4 2 * 1 5 - 2 3 ^ ^ / +
VBA
<lang VBA>Option Explicit Option Base 1
Function ShuntingYard(strInfix As String) As String Dim i As Long, j As Long, token As String, tokenArray() As String Dim stack() As Variant, queue() As Variant, discard As String Dim op1 As String, op2 As String
Debug.Print strInfix
' Get tokens tokenArray = Split(strInfix)
' Initialize array (removed later) ReDim stack(1) ReDim queue(1)
' Loop over tokens Do While 1
i = i + 1 If i - 1 > UBound(tokenArray) Then Exit Do Else token = tokenArray(i - 1) 'i-1 due to Split returning a Base 0 End If If token = "" Then: Exit Do
' Print Debug.Print i, token, Join(stack, ","), Join(queue, ",") ' If-loop over tokens (either brackets, operators, or numbers) If token = "(" Then stack = push(token, stack) ElseIf token = ")" Then While Peek(stack) <> "(" queue = push(pop(stack), queue) Wend discard = pop(stack) 'discard "(" ElseIf isOperator(token) Then op1 = token Do While (isOperator(Peek(stack)))
' Debug.Print Peek(stack)
op2 = Peek(stack) If op2 <> "^" And precedence(op1) = precedence(op2) Then '"^" is the only right-associative operator queue = push(pop(stack), queue) ElseIf precedence(op1$) < precedence(op2$) Then queue = push(pop(stack), queue) Else Exit Do End If Loop stack = push(op1, stack) Else 'number 'actually, wrong operator could end up here, like say % 'If the token is a number, then add it to the output queue. queue = push(CStr(token), queue) End If
Loop
While stack(1) <> ""
If Peek(stack) = "(" Then Debug.Print "no matching ')'": End queue = push(pop(stack), queue)
Wend
' Print final output ShuntingYard = Join(queue, " ") Debug.Print "Output:" Debug.Print ShuntingYard End Function
'------------------------------------------ Function isOperator(op As String) As Boolean
isOperator = InStr("+-*/^", op) <> 0 And Len(op$) = 1
End Function
Function precedence(op As String) As Integer
If isOperator(op$) Then precedence = 1 _ - (InStr("+-*/^", op$) <> 0) _ - (InStr("*/^", op$) <> 0) _ - (InStr("^", op$) <> 0) End If
End Function
'------------------------------------------ Function push(str, stack) As Variant Dim out() As Variant, i As Long If Not IsEmpty(stack(1)) Then
out = stack ReDim Preserve out(1 To UBound(stack) + 1) out(UBound(out)) = str
Else
ReDim out(1 To 1) out(1) = str
End If push = out End Function
Function pop(stack) pop = stack(UBound(stack)) If UBound(stack) > 1 Then
ReDim Preserve stack(1 To UBound(stack) - 1)
Else
stack(1) = ""
End If End Function
Function Peek(stack)
Peek = stack(UBound(stack))
End Function</lang>
- Output:
?ShuntingYard("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3") 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 1 3 2 + 3 3 4 + 3 4 * + 3,4 5 2 +,* 3,4 6 / +,* 3,4,2 7 ( +,/ 3,4,2,* 8 1 +,/,( 3,4,2,* 9 - +,/,( 3,4,2,*,1 10 5 +,/,(,- 3,4,2,*,1 11 ) +,/,(,- 3,4,2,*,1,5 12 ^ +,/ 3,4,2,*,1,5,- 13 2 +,/,^ 3,4,2,*,1,5,- 14 ^ +,/,^ 3,4,2,*,1,5,-,2 15 3 +,/,^,^ 3,4,2,*,1,5,-,2 Output: 3 4 2 * 1 5 - 2 3 ^ ^ / +
zkl
<lang zkl>var input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
var opa = D("^",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();
}</lang>
- Output:
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Token|3 Stack| Queue|3 Token|+ Stack|+ Queue|3 Token|4 Stack|+ Queue|3 4 Token|* Stack|+* Queue|3 4 Token|2 Stack|+* Queue|3 4 2 Token|/ Stack|+/ Queue|3 4 2 * Token|( Stack|+/( Queue|3 4 2 * Token|1 Stack|+/( Queue|3 4 2 * 1 Token|- Stack|+/(- Queue|3 4 2 * 1 Token|5 Stack|+/(- Queue|3 4 2 * 1 5 Token|) Stack|+/ Queue|3 4 2 * 1 5 - Token|^ Stack|+/^ Queue|3 4 2 * 1 5 - Token|2 Stack|+/^ Queue|3 4 2 * 1 5 - 2 Token|^ Stack|+/^^ Queue|3 4 2 * 1 5 - 2 Token|3 Stack|+/^^ Queue|3 4 2 * 1 5 - 2 3 postfix:3 4 2 * 1 5 - 2 3^ ^ / +