Parsing/Shunting-yard algorithm

From Rosetta Code
Jump to: navigation, search
Task
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

Contents

[edit] AutoHotkey

Works with: AutoHotkey_L
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

Simple with zero error handling; some extra credit.

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)
| True = (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
 

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.

{-# LANGUAGE LambdaCase #-}
import Control.Applicative
import Control.Lens
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. `process` is effectively foldM_ with the base case to
--format the output string
toRPN :: [InToken] -> Either String [OutToken]
toRPN xs = evalStateT (process (return ()) xs) ([],[])
where process st [] = st >> get >>= \(a,b) -> (reverse a++) <$>
(mapM toOut b)
process st (x:xs) = process (st >> processToken x) xs
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
 
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 ^ ^ / +

[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
┌─┬─┬─┬─┬─┐
13│+│*│+│
└─┴─┴─┴─┴─┘
 
NB. Boxed form useful for evaluation
algebra_to_rpn'0+666*(1+666*(2+666*(3)))' NB. polynomial evaluation.
┌─┬───┬─┬───┬─┬───┬─┬─┬─┬─┬─┬─┬─┐
0666166626663│*│+│*│+│*│+│
└─┴───┴─┴───┴─┴───┴─┴─┴─┴─┴─┴─┴─┘
 
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] Java

Works with: Java version 7
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")) {
char c = token.charAt(0);
int idx = ops.indexOf(c);
if (idx != -1 && token.length() == 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);
} else if (c == ')') {
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();
}
}

Output:

infix:   3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + 

[edit] 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);

Output:

infix:   3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + 

[edit] Liberty BASIC

 
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
 
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 ^ ^ / +

[edit] Perl

Translation of: Perl 6
use 5.010;
use strict;
use warnings;
 
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 ) {
given( shift @inp ) {
when ( /\d/ ) { $reduce->($_) }
when ( '(' ) { $shift->($_) }
when ( ')' ) { while( @ops and "(" ne (my $x = pop @ops) ) { $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->( pop @ops );
}
$shift->( $_ );
}
}
}
$reduce->( pop @ops ) while @ops;
@res;
}
 
local $, = " ";
say shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' ;
 
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 ^ ^ / +

[edit] Perl 6

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';
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 ^ ^ / +

[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] 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)))])])))
 
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" "^" "^" "/" "+")

[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 ^ ^ / +
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox