Parsing/Shunting-yard algorithm
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
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 ^ ^ / +
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 versions allows multi-character tokens (both operands and operators).
assume expression is correct
<lang rexx>/*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</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.*/
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</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 ^ ^ / +
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^ ^ / +