45 lines
1.2 KiB
Nim
45 lines
1.2 KiB
Nim
import tables, strutils, strformat
|
|
|
|
type operator = tuple[prec:int, rassoc:bool]
|
|
|
|
let ops = newTable[string, operator](
|
|
[ ("^", (4, true )),
|
|
("*", (3, false)),
|
|
("/", (3, false)),
|
|
("+", (2, false)),
|
|
("-", (2, false)) ])
|
|
|
|
proc shuntRPN(tokens:seq[string]): string =
|
|
var stack: seq[string]
|
|
var op:string
|
|
|
|
for token in tokens:
|
|
case token
|
|
of "(": stack.add token
|
|
of ")":
|
|
while stack.len > 0:
|
|
op = stack.pop()
|
|
if op == "(": break
|
|
result &= op & " "
|
|
else:
|
|
if token in ops:
|
|
while stack.len > 0:
|
|
op = stack[^1] # peek stack top
|
|
if not (op in ops): break
|
|
if ops[token].prec > ops[op].prec or (ops[token].rassoc and (ops[token].prec == ops[op].prec)):
|
|
break
|
|
discard stack.pop()
|
|
result &= op & " "
|
|
stack.add token
|
|
else:
|
|
result &= token & " "
|
|
echo fmt"""{token:5} {join(stack," "):18} {result:25} """
|
|
|
|
while stack.len > 0:
|
|
result &= stack.pop() & " "
|
|
echo fmt""" {join(stack," "):18} {result:25} """
|
|
|
|
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
|
|
|
|
echo &"for infix expression: '{input}' \n", "\nTOKEN OP STACK RPN OUTPUT"
|
|
echo "postfix: ", shuntRPN(input.strip.split)
|