Parsing/RPN calculator algorithm: Difference between revisions
(→Java) |
No edit summary |
||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
Create a stack-based evaluator for an expression in [[wp:Reverse Polish notation|reverse Polish notation]] that also shows the changes in the stack |
Create a stack-based evaluator for an expression in [[wp:Reverse Polish notation|reverse Polish notation]] that also shows the changes in the stack |
||
as each individual token is processed ''as a table''. |
as each individual token is processed ''as a table''. |
Revision as of 13:17, 11 April 2012
You are encouraged to solve this task according to the task description, using any language you may know.
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.
Ada
<lang Ada>with Ada.Text_IO, Ada.Containers.Vectors;
procedure RPN_Calculator is
package IIO is new Ada.Text_IO.Float_IO(Float);
package Float_Vec is new Ada.Containers.Vectors (Index_Type => Positive, Element_Type => Float); Stack: Float_Vec.Vector;
Input: String := Ada.Text_IO.Get_Line; Cursor: Positive := Input'First; New_Cursor: Positive;
begin
loop -- read spaces while Cursor <= Input'Last and then Input(Cursor)=' ' loop Cursor := Cursor + 1; end loop;
exit when Cursor > Input'Last;
New_Cursor := Cursor; while New_Cursor <= Input'Last and then Input(New_Cursor) /= ' ' loop New_Cursor := New_Cursor + 1; end loop;
-- try to read a number and push it to the stack declare Last: Positive; Value: Float; X, Y: Float; begin IIO.Get(From => Input(Cursor .. New_Cursor - 1), Item => Value, Last => Last); Stack.Append(Value); Cursor := New_Cursor;
exception -- if reading the number fails, try to read an operator token when others => Y := Stack.Last_Element; Stack.Delete_Last; -- pick two elements X := Stack.Last_Element; Stack.Delete_Last; -- from the stack case Input(Cursor) is when '+' => Stack.Append(X+Y); when '-' => Stack.Append(X-Y); when '*' => Stack.Append(X*Y); when '/' => Stack.Append(X/Y); when '^' => Stack.Append(X ** Integer(Float'Rounding(Y))); when others => raise Program_Error with "unecpected token '" & Input(Cursor) & "' at column" & Integer'Image(Cursor); end case; Cursor := New_Cursor; end;
for I in Stack.First_Index .. Stack.Last_Index loop Ada.Text_IO.Put(" "); IIO.Put(Stack.Element(I), Aft => 5, Exp => 0); end loop; Ada.Text_IO.New_Line; end loop;
Ada.Text_IO.Put("Result = "); IIO.Put(Item => Stack.Last_Element, Aft => 5, Exp => 0);
end RPN_Calculator;</lang>
Output:
3 4 2 * 1 5 - 2 3 ^ ^ / + 3.00000 3.00000 4.00000 3.00000 4.00000 2.00000 3.00000 8.00000 3.00000 8.00000 1.00000 3.00000 8.00000 1.00000 5.00000 3.00000 8.00000 -4.00000 3.00000 8.00000 -4.00000 2.00000 3.00000 8.00000 -4.00000 2.00000 3.00000 3.00000 8.00000 -4.00000 8.00000 3.00000 8.00000 65536.00000 3.00000 0.00012 3.00012 Result = 3.00012
ANTLR
Java
<lang java> grammar rpnC ; // // rpn Calculator // // Nigel Galloway - April 7th., 2012 // @members { Stack<Double> s = new Stack<Double>(); } rpn : (WS* (num|op) (WS | WS* NEWLINE {System.out.println(s.pop());}))*; num : '-'? Digit+ ('.' Digit+)? {s.push(Double.parseDouble($num.text));}; Digit : '0'..'9'; op : '-' {double x = s.pop(); s.push(s.pop() - x);} | '/' {double x = s.pop(); s.push(s.pop() / x);} | '*' {s.push(s.pop() * s.pop());} | '^' {double x = s.pop(); s.push(Math.pow(s.pop(), x));} | '+' {s.push(s.pop() + s.pop());}; WS : (' ' | '\t'){skip()}; NEWLINE : '\r'? '\n'; </lang> Produces:
>java Test 3 4 2 * 1 5 - 2 3 ^ ^ / + ^Z 3.0001220703125
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'
C#
<lang csharp>using System; using System.Collections.Generic; using System.Linq; using System.Globalization; using System.Threading;
namespace RPNEvaluator {
class RPNEvaluator { static void Main(string[] args) { Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
string rpn = "3 4 2 * 1 5 - 2 3 ^ ^ / +"; Console.WriteLine("{0}\n", rpn);
decimal result = CalculateRPN(rpn); Console.WriteLine("\nResult is {0}", result); }
static decimal CalculateRPN(string rpn) { string[] rpnTokens = rpn.Split(' '); Stack<decimal> stack = new Stack<decimal>(); decimal number = decimal.Zero;
foreach (string token in rpnTokens) { if (decimal.TryParse(token, out number)) { stack.Push(number); } else { switch (token) { case "^": case "pow": { number = stack.Pop(); stack.Push((decimal)Math.Pow((double)stack.Pop(), (double)number)); break; } case "ln": { stack.Push((decimal)Math.Log((double)stack.Pop(), Math.E)); break; } case "sqrt": { stack.Push((decimal)Math.Sqrt((double)stack.Pop())); break; } case "*": { stack.Push(stack.Pop() * stack.Pop()); break; } case "/": { number = stack.Pop(); stack.Push(stack.Pop() / number); break; } case "+": { stack.Push(stack.Pop() + stack.Pop()); break; } case "-": { number = stack.Pop(); stack.Push(stack.Pop() - number); break; } default: Console.WriteLine("Error in CalculateRPN(string) Method!"); break; } } PrintState(stack); }
return stack.Pop(); }
static void PrintState(Stack<decimal> stack) { decimal[] arr = stack.ToArray();
for (int i = arr.Length - 1; i >= 0; i--) { Console.Write("{0,-8:F3}", arr[i]); } Console.WriteLine(); } }
}</lang> Output:
3 4 2 * 1 5 - 2 3 ^ ^ / + 3.000 3.000 4.000 3.000 4.000 2.000 3.000 8.000 3.000 8.000 1.000 3.000 8.000 1.000 5.000 3.000 8.000 -4.000 3.000 8.000 -4.000 2.000 3.000 8.000 -4.000 2.000 3.000 3.000 8.000 -4.000 8.000 3.000 8.000 65536.000 3.000 0.000 3.000 Result is 3.0001220703125
Go
No error checking. <lang go>package main
import (
"fmt" "math" "strconv" "strings"
)
var input = "3 4 2 * 1 5 - 2 3 ^ ^ / +"
func main() {
fmt.Printf("For postfix %q\n", input) fmt.Println("\nToken Action Stack") var stack []float64 for _, tok := range strings.Fields(input) { action := "Apply op to top of stack" switch tok { case "+": stack[len(stack)-2] += stack[len(stack)-1] stack = stack[:len(stack)-1] case "-": stack[len(stack)-2] -= stack[len(stack)-1] stack = stack[:len(stack)-1] case "*": stack[len(stack)-2] *= stack[len(stack)-1] stack = stack[:len(stack)-1] case "/": stack[len(stack)-2] /= stack[len(stack)-1] stack = stack[:len(stack)-1] case "^": stack[len(stack)-2] = math.Pow(stack[len(stack)-2], stack[len(stack)-1]) stack = stack[:len(stack)-1] default: action = "Push num onto top of stack" f, _ := strconv.ParseFloat(tok, 64) stack = append(stack, f) } fmt.Printf("%3s %-26s %v\n", tok, action, stack) } fmt.Println("\nThe final value is", stack[0])
}</lang> Output:
For postfix "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 value is 3.0001220703125
Haskell
<lang Haskell>import Data.List (elemIndex)
-- Show results main = mapM_ (\(x, y) -> putStrLn $ x ++ " ==> " ++ show y) $ reverse $ zip b (a:c)
where (a, b, c) = solve "3 4 2 * 1 5 - 2 3 ^ ^ / +"
-- Solve and report RPN solve = foldl reduce ([], [], []) . words reduce (xs, ps, st) w =
if i == Nothing then (read w:xs, ("Pushing " ++ w):ps, xs:st) else (([(*),(+),(-),(/),(**)]!!o) a b:zs, ("Performing " ++ w):ps, xs:st) where i = elemIndex (head w) "*+-/^" Just o = i (b:a:zs) = xs
</lang> Output:
*Main> main Pushing 3 ==> [3.0] Pushing 4 ==> [4.0,3.0] Pushing 2 ==> [2.0,4.0,3.0] Performing * ==> [8.0,3.0] Pushing 1 ==> [1.0,8.0,3.0] Pushing 5 ==> [5.0,1.0,8.0,3.0] Performing - ==> [-4.0,8.0,3.0] Pushing 2 ==> [2.0,-4.0,8.0,3.0] Pushing 3 ==> [3.0,2.0,-4.0,8.0,3.0] Performing ^ ==> [8.0,-4.0,8.0,3.0] Performing ^ ==> [65536.0,8.0,3.0] Performing / ==> [1.220703125e-4,3.0] Performing + ==> [3.0001220703125] *Main>
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 ]
Java
Supports multi-digit numbers and negative numbers. <lang java5>import java.util.LinkedList;
public class RPN{ public static void evalRPN(String expr){ String cleanExpr = cleanExpr(expr); LinkedList<Double> stack = new LinkedList<Double>(); System.out.println("Input\tOperation\tStack after"); for(String token:cleanExpr.split("\\s")){ System.out.print(token+"\t"); Double tokenNum = null; try{ tokenNum = Double.parseDouble(token); }catch(NumberFormatException e){} if(tokenNum != null){ System.out.print("Push\t\t"); stack.push(Double.parseDouble(token+"")); }else if(token.equals("*")){ System.out.print("Operate\t\t"); double secondOperand = stack.pop(); double firstOperand = stack.pop(); stack.push(firstOperand * secondOperand); }else if(token.equals("/")){ System.out.print("Operate\t\t"); double secondOperand = stack.pop(); double firstOperand = stack.pop(); stack.push(firstOperand / secondOperand); }else if(token.equals("-")){ System.out.print("Operate\t\t"); double secondOperand = stack.pop(); double firstOperand = stack.pop(); stack.push(firstOperand - secondOperand); }else if(token.equals("+")){ System.out.print("Operate\t\t"); double secondOperand = stack.pop(); double firstOperand = stack.pop(); stack.push(firstOperand + secondOperand); }else if(token.equals("^")){ System.out.print("Operate\t\t"); double secondOperand = stack.pop(); double firstOperand = stack.pop(); stack.push(Math.pow(firstOperand, secondOperand)); }else{//just in case System.out.println("Error"); return; } System.out.println(stack); } System.out.println("Final answer: " + stack.pop()); }
private static String cleanExpr(String expr){ //remove all non-operators, non-whitespace, and non digit chars return expr.replaceAll("[^\\^\\*\\+\\-\\d/\\s]", ""); }
public static void main(String[] args){ evalRPN("3 4 2 * 1 5 - 2 3 ^ ^ / +"); } }</lang> Output:
Input Operation Stack after 3 Push [3.0] 4 Push [4.0, 3.0] 2 Push [2.0, 4.0, 3.0] * Operate [8.0, 3.0] 1 Push [1.0, 8.0, 3.0] 5 Push [5.0, 1.0, 8.0, 3.0] - Operate [-4.0, 8.0, 3.0] 2 Push [2.0, -4.0, 8.0, 3.0] 3 Push [3.0, 2.0, -4.0, 8.0, 3.0] ^ Operate [8.0, -4.0, 8.0, 3.0] ^ Operate [65536.0, 8.0, 3.0] / Operate [1.220703125E-4, 3.0] + Operate [3.0001220703125] Final answer: 3.0001220703125
Objeck
<lang objeck> use IO; use Struct;
bundle Default {
class RpnCalc { function : Main(args : String[]) ~ Nil { Caculate("3 4 2 * 1 5 - 2 3 ^ ^ / +"); } function : native : Caculate(rpn : String) ~ Nil { rpn->PrintLine(); tokens := rpn->Split(" "); stack := FloatVector->New(); each(i : tokens) { token := tokens[i]->Trim(); if(token->Size() > 0) { if(token->Get(0)->IsDigit()) { stack->AddBack(token->ToFloat()); } else { right := stack->Get(stack->Size() - 1); stack->RemoveBack(); left := stack->Get(stack->Size() - 1); stack->RemoveBack(); select(token->Get(0)) { label '+': { stack->AddBack(left + right); }
label '-': { stack->AddBack(left - right); }
label '*': { stack->AddBack(left * right); }
label '/': { stack->AddBack(left / right); }
label '^': { stack->AddBack(right->Power(left)); } }; }; PrintStack(stack); }; }; Console->Print("result: ")->PrintLine(stack->Get(0)); }
function : PrintStack(stack : FloatVector) ~ Nil { " ["->Print(); each(i : stack) { stack->Get(i)->Print(); if(i + 1< stack->Size()) { ", "->Print(); }; }; ']'->PrintLine(); } }
} </lang>
Output
3 4 2 * 1 5 - 2 3 ^ ^ / + [3] [3, 4] [3, 4, 2] [3, 8] [3, 8, 1] [3, 8, 1, 5] [3, 8, -4] [3, 8, -4, 2] [3, 8, -4, 2, 3] [3, 8, -4, 8] [3, 8, 65536] [3, 0.00012207] [3.00012] result: 3.00012
Perl
<lang Perl>
- RPN calculator
- Nigel Galloway April 2nd., 2012
$WSb = '(?:^|\s+)'; $WSa = '(?:\s+|$)'; $num = '([+-/]?(?:\.\d+|\d+(?:\.\d*)?))'; $op = '([-+*/^])'; sub myE {
my $a = '('.$1.')'.$3.'('.$2.')'; $a =~ s/\^/**/; return eval($a);
} while (<>) {
while (s/$WSb$num\s+$num\s+$op$WSa/' '.myE().' '/e) {} print ($_, "\n");
} </lang> Produces:
>rpnC.pl 3 4 2 * 1 5 - 2 3 ^ ^ / + 3.0001220703125
PHP
<lang php> <?php // RPN Calculator // // Nigel Galloway - April 3rd., 2012 // $WSb = '(?:^|\s+)'; $WSa = '(?:\s+|$)'; $num = '([+-]?(?:\.\d+|\d+(?:\.\d*)?))'; $op = '([-+*\/^])';
function myE($m) {
return $m[3] == '^' ? ' ' . pow($m[1], $m[2]) . ' ' : ' ' . eval("return " . $m[1] . $m[3] . $m[2] . ";") . ' ';
}
while (!feof(STDIN)) {
$s = trim(fgets(STDIN)); if ($s == ) continue; do { $s = preg_replace_callback("/$WSb$num\\s+$num\\s+$op$WSa/", "myE", $s, -1, $n); } while ($n); echo floatval($s) . "\n";
} ?> </lang> Produces:
3 4 2 * 1 5 - 2 3 ^ ^ / + 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
Run BASIC
<lang runbasic>prn$ = "3 4 2 * 1 5 - 2 3 ^ ^ / + "
j = 0 while word$(prn$,i + 1," ") <> "" i = i + 1
n$ = word$(prn$,i," ") if n$ < "0" or n$ > "9" then num1 = val(word$(stack$,s," ")) num2 = val(word$(stack$,s-1," ")) n = op(n$,num2,num1) s = s - 1 stack$ = stk$(stack$,s -1,str$(n)) print "Push Opr ";n$;" to stack: ";stack$ else s = s + 1 stack$ = stack$ + n$ + " " print "Push Num ";n$;" to stack: ";stack$
end if wend
function stk$(stack$,s,a$) for i = 1 to s
stk$ = stk$ + word$(stack$,i," ") + " "
next i stk$ = stk$ + a$ + " " end function
FUNCTION op(op$,a,b) if op$ = "*" then op = a * b if op$ = "/" then op = a / b if op$ = "^" then op = a ^ b if op$ = "+" then op = a + b if op$ = "-" then op = a - b end function</lang>
Push Num 3 to stack: 3 Push Num 4 to stack: 3 4 Push Num 2 to stack: 3 4 2 Push Opr * to stack: 3 8 Push Num 1 to stack: 3 8 1 Push Num 5 to stack: 3 8 1 5 Push Opr - to stack: 3 8 -4 Push Num 2 to stack: 3 8 -4 2 Push Num 3 to stack: 3 8 -4 2 3 Push Opr ^ to stack: 3 8 -4 8 Push Opr ^ to stack: 3 8 65536 Push Opr / to stack: 3 1.22070312e-4 Push Opr + to stack: 3.00012207
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