Parsing/RPN calculator algorithm: Difference between revisions

From Rosetta Code
Content added Content deleted
(Go solution)
Line 15: Line 15:
* [[Parsing/RPN to infix conversion]].
* [[Parsing/RPN to infix conversion]].
* [[Arithmetic evaluation]].
* [[Arithmetic evaluation]].

=={{header|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;
end loop;

while not Stack.Is_Empty loop
IIO.Put(Item => Stack.Last_Element, Aft => 5, Exp => 0);
Stack.Delete_Last;
end loop;

end RPN_Calculator;</lang>

Output:<pre>> ./rpn_calculator
3 4 2 * 1 5 - 2 3 ^ ^ / +
3.00012</pre>


=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==
Line 73: Line 143:


The final output value is: '3.000122'</pre>
The final output value is: '3.000122'</pre>

=={{header|Go}}==
=={{header|Go}}==
No error checking.
No error checking.

Revision as of 15:09, 13 January 2012

Parsing/RPN calculator algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

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;
  end loop;

  while not Stack.Is_Empty loop
     IIO.Put(Item => Stack.Last_Element, Aft => 5, Exp => 0);
     Stack.Delete_Last;
  end loop;

end RPN_Calculator;</lang>

Output:

> ./rpn_calculator 
3 4 2 * 1 5 - 2 3 ^ ^ / +
 3.00012

AutoHotkey

Works with: AutoHotkey_L

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'

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

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>

Library: Icon Programming Library

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
Retrieved from "https://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm?oldid=209157"