Parsing/Shunting-yard algorithm
From Rosetta Code
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.
Contents |
[edit] AutoHotkey
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) : ""
}
- 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 ^ ^ / + '
[edit] C
Requires a functioning ANSI terminal and Enter key.
#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;
}
- 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
[edit] Go
No error checking. No extra credit output, but there are some comments in the code.
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
}
Output:
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
[edit] Haskell
No error handling; extra credit.
import qualified Data.Map as M
import Text.Printf
import Data.List
import System.Environment
data Assoc = L | R deriving (Eq, Show)
data Op = Op Assoc Int
ops = M.fromList [("^", Op R 4)
,("*", Op L 3),("/", Op L 3)
,("+", Op L 2),("-", Op L 2)]
assoc t = case M.lookup t ops of
Just (Op a p) -> a
Nothing -> error "Bad lookup (assoc)"
prec t = case M.lookup t ops of
Just (Op a p) -> p
Nothing -> error "Bad lookup (prec)"
isDouble t = case reads t :: [(Double, String)] of
[(_, "")] -> True
_ -> False
finish (vs, fs, xs, _) = ((reverse fs ++ vs), [], xs, "Finished")
eval xs = (intermediates ++ [(finish $ last intermediates)])
where intermediates = scanl f ([], [], words xs, "").words $ xs
f (vs, fs, ts, msg) t | isDouble t = ((t:vs), fs, tail ts, "Writing '"
++ t)
| t `M.member` ops = pushOp t (vs, fs, ts, msg)
| t == "(" = (vs, (t:fs), tail ts, "Pushing '('")
| t == ")" = (((takeWhile (/="(") fs) ++ vs),
(tail $ dropWhile (/="(") fs),
tail ts, "Writing ops till ')'")
pushOp op1 (vs, fs, ts, msg) = if op2isOp &&
((assoc op1 == L && prec op1 <= prec op2) ||
(prec op1 < prec op2))
then ((op2:vs), (op1:tail fs), tail ts,
"Writing '" ++ op2 ++
"', pushing " ++ op1)
else (vs, (op1:fs), tail ts, "Pushing '" ++ op1 ++ "'")
where (op2isOp, op2) = ((not $ null fs) && (op2 `M.member` ops), head fs)
showData (vs, fs, xs, msg) = concat [printf "%30s" (intercalate " " (reverse vs)) , " "
,printf "%10s" (intercalate " " fs) , " "
,printf "%35s" (intercalate " " xs) , " "
,printf "%s" msg]
showAll xs = intercalate "\n" $ map showData xs
main = do putStrLn.showAll.eval $ "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
Output:
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Writing '3
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Pushing '+'
3 4 + * 2 / ( 1 - 5 ) ^ 2 ^ 3 Writing '4
3 4 * + 2 / ( 1 - 5 ) ^ 2 ^ 3 Pushing '*'
3 4 2 * + / ( 1 - 5 ) ^ 2 ^ 3 Writing '2
3 4 2 * / + ( 1 - 5 ) ^ 2 ^ 3 Writing '*', pushing /
3 4 2 * ( / + 1 - 5 ) ^ 2 ^ 3 Pushing '('
3 4 2 * 1 ( / + - 5 ) ^ 2 ^ 3 Writing '1
3 4 2 * 1 - ( / + 5 ) ^ 2 ^ 3 Pushing '-'
3 4 2 * 1 5 - ( / + ) ^ 2 ^ 3 Writing '5
3 4 2 * 1 5 - / + ^ 2 ^ 3 Writing ops till ')'
3 4 2 * 1 5 - ^ / + 2 ^ 3 Pushing '^'
3 4 2 * 1 5 - 2 ^ / + ^ 3 Writing '2
3 4 2 * 1 5 - 2 ^ ^ / + 3 Pushing '^'
3 4 2 * 1 5 - 2 3 ^ ^ / + Writing '3
3 4 2 * 1 5 - 2 3 ^ ^ / + Finished
[edit] Icon and Unicon
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
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 ^ ^ / + "
[edit] J
Code
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
Demonstration
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 ^ ^ / +
[edit] PicoLisp
Note: "^" is a meta-character and must be escaped in strings
(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) ) ) ) )
Output:
: (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 "\^" "\^" "/" "+")
[edit] 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;
Output:
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 ^ ^ / +
[edit] Python
Parenthesis are added to the operator table then special-cased in the code. This solution includes the extra credit.
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])
- 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 ^ ^ / +'
[edit] REXX
These versions allows multi-character tokens (both operands and operators).
[edit] assume expression is correct
/*REXX pgm converts infix arith. 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*/ /*assign input tokens*/
L=max(20,length(x)) /*use 20 for the min show width. */
say 'token' center('input',L,'─') center('stack',L%2,'─') 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 /*i*/
/*[↑] assign operator priorities.*/
do #=1 for tokens; ?=@.# /*process each token from @. list*/
select /*@.# is: (, operator, ), operand*/
when ?=='(' then do; stack='(' stack; call show 'moving' ? "──► stack"; end
when isOp(?) then do /*is token an operator?*/
!=word(stack,1) /*get token from stack.*/
do while !\==')' & s.!>=p.?; RPN=RPN ! /*add*/
stack=subword(stack,2); /*del token from stack.*/
call show 'unstacking:' !
!=word(stack,1) /*get token from stack.*/
end /*while ···)*/
stack=? stack /*add token to stack.*/
call show 'moving' ? "──► stack"
end
when ?==')' then do; !=word(stack,1) /*get token from stack.*/
do while !\=='('; RPN=RPN ! /*add to RPN.*/
stack=subword(stack,2) /*del token from stack.*/
!=word(stack,1) /*get token from stack.*/
call show 'moving stack' ! '──► RPN'
end /*while ···( */
stack=subword(stack,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 /*#*/
RPN=space(RPN stack)
say; say 'input:' ox; say 'RPN──►' RPN /*show input and the RPN.*/
parse source upper . y . /*invoked via C.L. or REXX pgm?*/
if y=='COMMAND' then exit /*stick a fork in it, we're done.*/
else return RPN /*return RPN to invoker (RESULT).*/
/*──────────────────────────────────ISOP subroutine─────────────────────*/
isOp: return pos(arg(1),rOp)\==0 /*is argument1 a "real" operator?*/
/*──────────────────────────────────SHOW subroutine─────────────────────*/
show: if showSteps then say center(?,length(pad)) left(subword(x,#),L),
left(stack,L%2) left(space(RPN),L) arg(1); return
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 ^ ^ / +
[edit] 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.
/*REXX pgm converts infix arith. expressions to Reverse Polish notation.*/
parse arg x; if x='' then x = '3 + 4 * 2 / ( ( 1 - 5 ) ) ^ 2 ^ 3'; ox=x
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=-1e9; end
end /*p*/
good=(g==0) /*indicate expression is good | ¬*/
showSteps=1 /* 0: action steps not wanted.*/
x='(' space(x) ') '; tokens=words(x) /*force stacking for expression. */
do i=1 for tokens; @.i=word(x,i); end /*i*/ /*assign input tokens*/
L=max(20,length(x)) /*use 20 for the min show width. */
if good then say 'token' center('input' ,L,'─') center('stack' ,L%2,'─'),
center('output',L,'─') center('action',L ,'─')
pad=left('',5); op=')(-+/*^'; rOp=substr(op,3); stack=
p.=; n=length(op); s.=; RPN=
do i=1 for n; _=substr(op,i,1); s._=(i+1)%2; p._=s._+(i==n); end /*i*/
/*[↑] assign operator priorities.*/
do #=1 for tokens*good; ?=@.# /*process each token from @. list*/
select /*@.# is: (, operator, ), operand*/
when ?=='(' then do; stack='(' stack; call show 'moving' ? "──► stack"; end
when isOp(?) then do /*is token an operator?*/
!=word(stack,1) /*get token from stack.*/
do while !\==')' & s.!>=p.?; RPN=RPN ! /*add*/
stack=subword(stack,2); /*del token from stack.*/
call show 'unstacking:' !
!=word(stack,1) /*get token from stack.*/
end /*while ···)*/
stack=? stack /*add token to stack.*/
call show 'moving' ? "──► stack"
end
when ?==')' then do; !=word(stack,1) /*get token from stack.*/
do while !\=='('; RPN=RPN ! /*add to RPN.*/
stack=subword(stack,2) /*del token from stack.*/
!=word(stack,1) /*get token from stack.*/
call show 'moving stack' ! '──► RPN'
end /*while ···( */
stack=subword(stack,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 /*#*/
RPN=space(RPN stack)
if \good then RPN = '─────── error in expression ───────'
say; say ' input:' ox; say ' RPN──►' RPN /*show input and the RPN.*/
parse source upper . y . /*invoked via C.L. or REXX pgm?*/
if y=='COMMAND' then exit /*stick a fork in it, we're done.*/
else return RPN /*return RPN to invoker (RESULT).*/
/*──────────────────────────────────ISOP subroutine─────────────────────*/
isOp: return pos(arg(1),rOp)\==0 /*is argument1 a "real" operator?*/
/*──────────────────────────────────SHOW subroutine─────────────────────*/
show: if showSteps then say center(?,length(pad)) left(subword(x,#),L),
left(stack,L%2) left(space(RPN),L) arg(1); return
output when using the input: ) (
input: ) ( RPN──► ─────── error in expression ───────
[edit] Ruby
See Parsing/RPN/Ruby
rpn = RPNExpression.from_infix("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")
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 ^ ^ / +
[edit] 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"]
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 ^ ^ / +
