Parsing/Shunting-yard algorithm
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:
You are encouraged to solve this task according to the task description, using any language you may know.
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
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 ^ ^ / +
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>
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 ^ ^ / +'
REXX
<lang rexx>/*REXX pgm to convert arithmetic expressions to Reverse Polish notation.*/ parse arg x; if x= then x = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'; ox=x showSteps=1 /*set to 0 (zero) if working steps not wanted.*/ x='(' space(x) ') '; tokens=words(x) /*force stacking for expression. */
do i=1 for tokens; @.i=word(x,i); end /*i*/ /*define input tokens*/
L=max(20,length(x)) /*use 20 for the min show width. */ say 'token' center('input',L,'─') center('stack',L%4,'─') center('output',L,'─') center('action',L,'─') pad=left(,5); op=')(-+/*^'; rop=substr(op,3); p.=; s.=; n=length(op); RPN=; stack=
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end
/*[↑] assign operator priorities.*/
do #=1 for tokens /*keep truckin' until tokens done*/
?=@.# /*pick off token from the input. */
select
when ?=='(' then do; stack='('stack; call show 'moving' ? "──► stack"; end
when pos(?,rop)\==0 then /*is token an operator ? */
do
!=left(stack,1) /*get a token from stack.*/
do while !\==')' & s.!>=p.?
RPN=RPN ! /*add a token to RPN out.*/
call show 'unstacking:' !
stack=substr(stack,2); /*elide token from stack.*/
!=left(stack,1) /*get a token from stack.*/
end /*while ···)*/
call show 'moving' ? "──► stack"
stack=? || stack /*add token to the stack.*/
end
when ?==')' then do
!=left(stack,1) /*get a token from stack.*/
do while !\=='('
call show 'moving stack' ! '──► RPN'
RPN=RPN ! /*add a token to RPN out.*/
stack=substr(stack,2) /*elide token from stack.*/
!=left(stack,1) /*get a token from stack.*/
end /*while ···( */
stack=substr(stack,2) /*elide token from stack.*/
call show 'deleting ( from the stack'
end
otherwise RPN=RPN ? /*add the operand to RPN output. */
call show 'moving' ? '──► RPN'
end /*select*/
end /*#*/
say; say 'input:' ox; say 'RPN──►' space(RPN) parse source upper . how . /*invoked via C.L. or REXX pgm?*/ if how=='COMMAND' then exit /*stick a fork in it, we're done.*/
else return space(RPN) /*return RPN to invoker */
/*──────────────────────────────────SHOW subroutines────────────────────*/ show: if showSteps then say center(?,length(pad)) left(subword(x,#),L),
left(stack,L%4) left(space(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 ^ ^ / +
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 ^ ^ / +
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 ^ ^ / +