Parsing/RPN calculator algorithm: Difference between revisions
(Added PicoLisp) |
|||
Line 158: | Line 158: | ||
-> 3</lang> |
-> 3</lang> |
||
=={{header|Prolog}}== |
|||
Works with SWI-Prolog. |
|||
<lang Prolog>rpn(L) :- |
|||
writeln('Token Action Stack'), |
|||
parse(L, [],[X] ,[]), |
|||
format('~nThe final output value is ~w~n', [X]). |
|||
% skip spaces |
|||
parse([X|L], St) --> |
|||
{char_type(X, white)}, |
|||
parse(L, St). |
|||
% detect operators |
|||
parse([Op|L], [Y, X | St]) --> |
|||
{ is_op(Op, X, Y, V), |
|||
writef(' %s', [[Op]]), |
|||
with_output_to(atom(Str2), writef('Apply %s on top of stack', [[Op]])), |
|||
writef(' %35l', [Str2]), |
|||
writef('%w\n', [[V | St]])}, |
|||
parse(L, [V | St]). |
|||
% detect number |
|||
parse([N|L], St) --> |
|||
{char_type(N, digit)}, |
|||
parse_number(L, [N], St). |
|||
% string is finished |
|||
parse([], St) --> St. |
|||
% compute numbers |
|||
parse_number([N|L], NC, St) --> |
|||
{char_type(N, digit)}, |
|||
parse_number(L, [N|NC], St). |
|||
parse_number(S, NC, St) --> |
|||
{ reverse(NC, RNC), |
|||
number_chars(V, RNC), |
|||
writef('%5r', [V]), |
|||
with_output_to(atom(Str2), writef('Push num %w on top of stack', [V])), |
|||
writef(' %35l', [Str2]), |
|||
writef('%w\n', [[V | St]])}, |
|||
parse(S, [V|St]). |
|||
% defining operations |
|||
is_op(42, X, Y, V) :- V is X*Y. |
|||
is_op(43, X, Y, V) :- V is X+Y. |
|||
is_op(45, X, Y, V) :- V is X-Y. |
|||
is_op(47, X, Y, V) :- V is X/Y. |
|||
is_op(94, X, Y, V) :- V is X**Y. |
|||
</lang> |
|||
Output : |
|||
<pre>5 ?- rpn("3 4 2 * 1 5 - 2 3 ^ ^ / +"). |
|||
Token Action Stack |
|||
3 'Push num 3 on top of stack' [3] |
|||
4 'Push num 4 on top of stack' [4,3] |
|||
2 'Push num 2 on top of stack' [2,4,3] |
|||
* 'Apply * on top of stack' [8,3] |
|||
1 'Push num 1 on top of stack' [1,8,3] |
|||
5 'Push num 5 on top of stack' [5,1,8,3] |
|||
- 'Apply - on top of stack' [-4,8,3] |
|||
2 'Push num 2 on top of stack' [2,-4,8,3] |
|||
3 'Push num 3 on top of stack' [3,2,-4,8,3] |
|||
^ 'Apply ^ on top of stack' [8,-4,8,3] |
|||
^ 'Apply ^ on top of stack' [65536,8,3] |
|||
/ 'Apply / on top of stack' [0.0001220703125,3] |
|||
+ 'Apply + on top of stack' [3.0001220703125] |
|||
The final output value is 3.0001220703125 |
|||
true .</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
Revision as of 14:12, 11 January 2012
Create a stack-based evaluator for an expression in reverse Polish notation that also shows the changes in the stack as each individual token is processed as a table.
- Assume an input of a correct, space separated, string of tokens of an RPN expression
- Test with the RPN expression generated from the Parsing/Shunting-yard algorithm task
'3 4 2 * 1 5 - 2 3 ^ ^ / +'
then print and display the output here.
- Note
- '^' means exponentiation in the expression above.
- See also
- Parsing/Shunting-yard algorithm for a method of generating an RPN from an infix expression.
- Several solutions to 24 game/Solve make use of RPN evaluators (although tracing how they work is not a part of that task).
- Parsing/RPN to infix conversion.
- Arithmetic evaluation.
AutoHotkey
Output is in clipboard. <lang AHK>evalRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +") evalRPN(s){ stack := [] out := "For RPN expression: '" s "'`r`n`r`nTOKEN`t`tACTION`t`t`tSTACK`r`n" Loop Parse, s If A_LoopField is number t .= A_LoopField else { If t stack.Insert(t) , out .= t "`tPush num onto top of stack`t" stackShow(stack) "`r`n" , t := "" If InStr("+-/*^", l := A_LoopField) { a := stack.Remove(), b := stack.Remove() stack.Insert( l = "+" ? b + a :l = "-" ? b - a :l = "*" ? b * a :l = "/" ? b / a :l = "^" ? b **a :0 ) out .= l "`tApply op " l " to top of stack`t" stackShow(stack) "`r`n" } } r := stack.Remove() out .= "`r`n The final output value is: '" r "'" clipboard := out return r } StackShow(stack){ for each, value in stack out .= A_Space value return subStr(out, 2) }</lang>
- Output
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +' TOKEN ACTION STACK 3 Push num onto top of stack 3 4 Push num onto top of stack 3 4 2 Push num onto top of stack 3 4 2 * Apply op * to top of stack 3 8 1 Push num onto top of stack 3 8 1 5 Push num onto top of stack 3 8 1 5 - Apply op - to top of stack 3 8 -4 2 Push num onto top of stack 3 8 -4 2 3 Push num onto top of stack 3 8 -4 2 3 ^ Apply op ^ to top of stack 3 8 -4 8 ^ Apply op ^ to top of stack 3 8 65536 / Apply op / to top of stack 3 0.000122 + Apply op + to top of stack 3.000122 The final output value is: '3.000122'
Icon and Unicon
<lang Icon>procedure main()
EvalRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +")
end
link printf invocable all
procedure EvalRPN(expr) #: evaluate (and trace stack) an RPN string
stack := [] expr ? until pos(0) do { tab(many(' ')) # consume previous seperator token := tab(upto(' ')|0) # get token if token := numeric(token) then { # ... numeric push(stack,token) printf("pushed numeric %i : %s\n",token,list2string(stack)) } else { # ... operator every b|a := pop(stack) # pop & reverse operands case token of { "+"|"-"|"*"|"^" : push(stack,token(a,b)) "/" : push(stack,token(real(a),b)) default : runerr(205,token) } printf("applied operator %s : %s\n",token,list2string(stack)) } }
end
procedure list2string(L) #: format list as a string
every (s := "[ ") ||:= !L || " " return s || "]"
end</lang>
printf.icn provides formatting
Output:
pushed numeric 3 : [ 3 ] pushed numeric 4 : [ 4 3 ] pushed numeric 2 : [ 2 4 3 ] applied operator * : [ 8 3 ] pushed numeric 1 : [ 1 8 3 ] pushed numeric 5 : [ 5 1 8 3 ] applied operator - : [ -4 8 3 ] pushed numeric 2 : [ 2 -4 8 3 ] pushed numeric 3 : [ 3 2 -4 8 3 ] applied operator ^ : [ 8 -4 8 3 ] applied operator ^ : [ 65536 8 3 ] applied operator / : [ 0.0001220703125 3 ] applied operator + : [ 3.0001220703125 ]
PicoLisp
This is an integer-only calculator: <lang PicoLisp>(de rpnCalculator (Str)
(let (^ ** Stack) # Define '^' from the built-in '**' (prinl "Token Stack") (for Token (str Str "*+-/\^") (if (num? Token) (push 'Stack @) (set (cdr Stack) (Token (cadr Stack) (pop 'Stack)) ) ) (prin Token) (space 6) (println Stack) ) (println (car Stack)) ) )</lang>
Test (note that the top-of-stack is in the left-most position): <lang PicoLisp>: (rpnCalculator "3 4 2 * 1 5 - 2 3 \^ \^ / +") Token Stack 3 (3) 4 (4 3) 2 (2 4 3)
- (8 3)
1 (1 8 3) 5 (5 1 8 3) - (-4 8 3) 2 (2 -4 8 3) 3 (3 2 -4 8 3) ^ (8 -4 8 3) ^ (65536 8 3) / (0 3) + (3) 3 -> 3</lang>
Prolog
Works with SWI-Prolog. <lang Prolog>rpn(L) :- writeln('Token Action Stack'), parse(L, [],[X] ,[]), format('~nThe final output value is ~w~n', [X]).
% skip spaces
parse([X|L], St) -->
{char_type(X, white)},
parse(L, St).
% detect operators parse([Op|L], [Y, X | St]) --> { is_op(Op, X, Y, V), writef(' %s', Op), with_output_to(atom(Str2), writef('Apply %s on top of stack', Op)), writef(' %35l', [Str2]), writef('%w\n', St)}, parse(L, [V | St]).
% detect number parse([N|L], St) --> {char_type(N, digit)}, parse_number(L, [N], St).
% string is finished parse([], St) --> St.
% compute numbers parse_number([N|L], NC, St) --> {char_type(N, digit)}, parse_number(L, [N|NC], St).
parse_number(S, NC, St) --> { reverse(NC, RNC), number_chars(V, RNC), writef('%5r', [V]), with_output_to(atom(Str2), writef('Push num %w on top of stack', [V])), writef(' %35l', [Str2]), writef('%w\n', St)}, parse(S, [V|St]).
% defining operations is_op(42, X, Y, V) :- V is X*Y. is_op(43, X, Y, V) :- V is X+Y. is_op(45, X, Y, V) :- V is X-Y. is_op(47, X, Y, V) :- V is X/Y. is_op(94, X, Y, V) :- V is X**Y. </lang> Output :
5 ?- rpn("3 4 2 * 1 5 - 2 3 ^ ^ / +"). Token Action Stack 3 'Push num 3 on top of stack' [3] 4 'Push num 4 on top of stack' [4,3] 2 'Push num 2 on top of stack' [2,4,3] * 'Apply * on top of stack' [8,3] 1 'Push num 1 on top of stack' [1,8,3] 5 'Push num 5 on top of stack' [5,1,8,3] - 'Apply - on top of stack' [-4,8,3] 2 'Push num 2 on top of stack' [2,-4,8,3] 3 'Push num 3 on top of stack' [3,2,-4,8,3] ^ 'Apply ^ on top of stack' [8,-4,8,3] ^ 'Apply ^ on top of stack' [65536,8,3] / 'Apply / on top of stack' [0.0001220703125,3] + 'Apply + on top of stack' [3.0001220703125] The final output value is 3.0001220703125 true .
Python
<lang python>def op_pow(stack):
b = stack.pop(); a = stack.pop() stack.append( a ** b )
def op_mul(stack):
b = stack.pop(); a = stack.pop() stack.append( a * b )
def op_div(stack):
b = stack.pop(); a = stack.pop() stack.append( a / b )
def op_add(stack):
b = stack.pop(); a = stack.pop() stack.append( a + b )
def op_sub(stack):
b = stack.pop(); a = stack.pop() stack.append( a - b )
def op_num(stack, num):
stack.append( num )
ops = {
'^': op_pow, '*': op_mul, '/': op_div, '+': op_add, '-': op_sub, }
def get_input(inp = None):
'Inputs an expression and returns list of tokens' if inp is None: inp = input('expression: ') tokens = inp.strip().split() return tokens
def rpn_calc(tokens):
stack = [] table = ['TOKEN,ACTION,STACK'.split(',')] for token in tokens: if token in ops: action = 'Apply op to top of stack' ops[token](stack) table.append( (token, action, ' '.join(str(s) for s in stack)) ) else: action = 'Push num onto top of stack' op_num(stack, eval(token)) table.append( (token, action, ' '.join(str(s) for s in stack)) ) return table
if __name__ == '__main__':
rpn = '3 4 2 * 1 5 - 2 3 ^ ^ / +' print( 'For RPN expression: %r\n' % rpn ) rp = rpn_calc(get_input(rpn)) maxcolwidths = [max(len(y) for y in x) 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 value is: %r' % rp[-1][2])</lang>
- Output
For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +' TOKEN ACTION STACK 3 Push num onto top of stack 3 4 Push num onto top of stack 3 4 2 Push num onto top of stack 3 4 2 * Apply op to top of stack 3 8 1 Push num onto top of stack 3 8 1 5 Push num onto top of stack 3 8 1 5 - Apply op to top of stack 3 8 -4 2 Push num onto top of stack 3 8 -4 2 3 Push num onto top of stack 3 8 -4 2 3 ^ Apply op to top of stack 3 8 -4 8 ^ Apply op to top of stack 3 8 65536 / Apply op to top of stack 3 0.0001220703125 + Apply op to top of stack 3.0001220703125 The final output value is: '3.0001220703125'
Ruby
See Parsing/RPN/Ruby
<lang ruby>rpn = RPNExpression("3 4 2 * 1 5 - 2 3 ^ ^ / +") value = rpn.eval</lang> outputs
for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / + Term Action Stack 3 PUSH [3] 4 PUSH [3, 4] 2 PUSH [3, 4, 2] * MUL [3, 8] 1 PUSH [3, 8, 1] 5 PUSH [3, 8, 1, 5] - SUB [3, 8, -4] 2 PUSH [3, 8, -4, 2] 3 PUSH [3, 8, -4, 2, 3] ^ EXP [3, 8, -4, 8] ^ EXP [3, 8, 65536] / DIV [3, 0.0001220703125] + ADD [3.0001220703125] Value = 3.0001220703125
Tcl
<lang tcl># Helper proc pop stk {
upvar 1 $stk s set val [lindex $s end] set s [lreplace $s end end] return $val
}
proc evaluate rpn {
set stack {} foreach token $rpn {
set act "apply" switch $token { "^" { # Non-commutative operation set a [pop stack] lappend stack [expr {[pop stack] ** $a}] } "/" { # Non-commutative, special float handling set a [pop stack] set b [expr {[pop stack] / double($a)}] if {$b == round($b)} {set b [expr {round($b)}]} lappend stack $b } "*" { # Commutative operation lappend stack [expr {[pop stack] * [pop stack]}] } "-" { # Non-commutative operation set a [pop stack] lappend stack [expr {[pop stack] - $a}] } "+" { # Commutative operation lappend stack [expr {[pop stack] + [pop stack]}] } default { set act "push" lappend stack $token } } puts "$token\t$act\t$stack"
} return [lindex $stack end]
}
puts [evaluate {3 4 2 * 1 5 - 2 3 ^ ^ / +}]</lang> Output:
3 push 3 4 push 3 4 2 push 3 4 2 * apply 3 8 1 push 3 8 1 5 push 3 8 1 5 - apply 3 8 -4 2 push 3 8 -4 2 3 push 3 8 -4 2 3 ^ apply 3 8 -4 8 ^ apply 3 8 65536 / apply 3 0.0001220703125 + apply 3.0001220703125 3.0001220703125