# Arithmetic

Arithmetic using Reverse Polish Notation (RPN)

## Introduction

Program Arithmetic converts an arithmetic expression of numbers to reverse Polish notation (RPN) and then evaluates the expression. Peter began program Arithmetic using in-line assembler and then found it easier to extend its functionality by rewriting it in Pascal. We have studied the code carefully and provide some notes to guide you through it. You may find it helpful to read our tutorial section on stacks first.

ExpressionArray[expressionArrayLength] := ExpressionArray[expressionArrayLength] + currentChar;

In the case of an operator, expressionArrayLength is incremented so that currentChar is added to an empty string. The `-` operator must be a unary operator if it follows another operator and serves to negate the number following it. Peter includes the `-` in the string with the number following it so that the strtoReal function will convert the string to a negative number.

A parallel array, ExpressionArrayIsOperator, indicates whether each string is an operator (1) or not (0).

The number strings are converted to real numbers and stored in VariableStorageArray. VariablisedExpressionArray, parallel to VariableStorageArray, contains a single letter identifier for each number. The program outputs each identifier and the number it represents.

The following algorithms for converting from our usual format for expressions (infix) to RPN and for evaluating RPN are adapted from those given by Geoffrey Knott and Nick Waites in *Computing* (published by Business Education Publishers Limited).

- If the incoming symbol is a variable or constant, copy it to the RPN output.
- If the incoming symbol is an operator or of higher precedence than the operator at the top of the stack, or if the stack is empty, push the operator onto the stack.
- If the incoming symbol is an operator or of equal or lower precedence than the operator at the top of the stack, pop the stack to the output stream and go to step 2 using the current symbol.
- The left bracket, (, goes on top of the operator stack and remains there until released by ).
- The right bracket, ), releases all operators to the output stack until ( is reached. The left bracket is popped from the stack but is not used. RPN does not need brackets because the order of operations is strictly predetermined.
- When the end of the input stream is reached, any operators remaining on the stack are released to the RPN stream, completing the conversion.

*scan*(taken from its use in lexical analysis) means that the stream of characters making up the input is read one at a time and processed. The stack is used to hold all the operands which have been scanned or have been produced as a result of some operation but have not been used. The algorithm for evaluating an expression in RPN in a single scan is:

- If the scanned symbol is a variable or constant, push its value to the stack and scan the next symbol.
- If the scanned symbol is a binary operator, pop the two topmost values on the stack, apply the operation to them and then push the result to the stack.
- If the scanned symbol is a unary operator, pop the top of the stack, apply the operation to this item and then push the result to the stack. (Peter applies the unary operator - before converting to RPN and does not require this step).

## The Program

program Arithmetic; { Copyright (c) 2011 Peter Hearnshaw Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License, as described at http://www.apache.org/licenses/ and http://www.pp4s.co.uk/licenses/ } {$APPTYPE CONSOLE} uses Classes, SysUtils, strutils; var inputStr : string; ExpressionArray : array[1 .. 80] of string; ExpressionArrayIsOperator : array[1 .. 80] of byte; //this runs parallel to ExpressionArray, stating whether its value is a number or operator ExpressionArrayLength : integer; VariablisedExpressionArray : array[1 .. 80] of byte; VariableStorageArray : array[1..35] of real; RPNVariablisedExpressionArray : array[1 .. 80] of byte; i, RPNcount : integer; isOperator : boolean = false; currentChar : char; tempString : string; numOfVariables : integer = 0; Popped, Scanned, CurrentChrByte : byte; finalAnswer, tempReal1, tempReal2 : real; myRealStack : array [1 .. 100] of real; indexOfTopOfStack : integer = 0; function stackPop : real; begin stackPop := myRealStack[indexOfTopOfStack]; dec(indexOfTopOfStack); end; procedure stackPush (value : real); begin inc(indexOfTopOfStack); myRealStack[indexOfTopOfStack] := value; end; begin for i := 1 to 80 do ExpressionArray[i] := ''; writeln('Please input an expression (with no spaces): '); readln(inputStr); //inputStr := '(1+2.5*(2.762+53.1*(2+-5*-4*(2+3)))+-61.7)'; writeln('Expression: ', inputStr); //PROCESS INITIAL EXPRESSION expressionArrayLength := 0; currentChar := inputStr[1]; if (ord(currentChar) > 47) then expressionArrayLength := 1; //expressionArrayLength becomes one if first char is a number because //numbers will be added to the end of the current array position on line 75 for i := 1 to length(inputStr) do begin currentChar := inputStr[i]; //if current char is - and last char was an operator other than ) if (ord(currentChar) = 45) and (isOperator = true) and (ord(inputStr[i - 1]) <> 41) then begin isOperator := false; inc(expressionArrayLength); ExpressionArrayIsOperator[expressionArrayLength] := 0; end else begin if (ord(currentChar) < 48) and (ord(currentChar) <> 46) then begin isOperator := true; inc(expressionArrayLength); ExpressionArrayIsOperator[expressionArrayLength] := 1; end; if (ord(currentChar) > 47) and (isOperator = true) then begin isOperator := false; inc(expressionArrayLength); ExpressionArrayIsOperator[expressionArrayLength] := 0; end; end; ExpressionArray[expressionArrayLength] := ExpressionArray[expressionArrayLength] + currentChar; end; //VARIABLISE EXPRESSION //by variablising I mean turning 41 + 21 into a + b, 'a' stored in array as 41 and 'b' as 21 numOfVariables := 0; for i := 1 to expressionArrayLength do begin if (ExpressionArrayIsOperator[i] = 0) then //i.e. is a number begin inc(numOfVariables); tempString := ExpressionArray[i]; VariableStorageArray[numOfVariables] := strtofloat(tempString); VariablisedExpressionArray[i] := 96 + numOfVariables; //first variable will be 'a' then 'b'... end; if (ExpressionArrayIsOperator[i] = 1) then //i.e. is an operator begin tempString := ExpressionArray[i]; VariablisedExpressionArray[i] := ord(tempString[1]); end; end; //PRINT OUT write('Expression In Variables: '); for i := 1 to expressionArrayLength do begin write(chr(VariablisedExpressionArray[i])); if (i <> expressionArrayLength) then write(','); end; writeln; writeln('Variables:'); for i := 1 to numOfVariables do begin write(' ', chr(96 + i) ,' = '); writeln(VariableStorageArray[i] : 1 : 5); end; finalAnswer := 0; /////CONVERT TO REVERSE POLISH NOTATION indexOfTopOfStack := 0; RPNcount := 0; for i := 1 to expressionArrayLength do begin if VariablisedExpressionArray[i] > 47 then //is a number begin inc(RPNcount); RPNVariablisedExpressionArray[RPNcount] := VariablisedExpressionArray[i]; end; if VariablisedExpressionArray[i] < 48 then //is an operator begin //Don't bother at all with this if there isn't anything on the stack if (indexOfTopOfStack <> 0) and (VariablisedExpressionArray[i] <> 40)and (VariablisedExpressionArray[i] <> 41)then begin repeat popped := round(stackPop); stackPush(popped); if (popped = 40) then begin scanned := 100; //This makes sure the program will escape the repeat, to immediately push the operator end else begin //poppedItem := popped; if (popped = 42) or (popped = 47) then // * or / begin popped := 2; //priority 2 end else begin popped := 1; //priority 1 end; scanned := VariablisedExpressionArray[i]; if (scanned = 42) or (scanned = 47) then begin scanned := 2; //priority 2 end else begin scanned := 1; //priority 1 end; if (scanned <= popped) then // Pop the stack to the end of the RPN array begin inc(RPNcount); popped := round(stackPop); RPNVariablisedExpressionArray[RPNcount] := popped; end; end; until (scanned > popped) or (indexOfTopOfStack = 0); end; stackPush(VariablisedExpressionArray[i]); //VERY important if (VariablisedExpressionArray[i] = 41) then begin stackPop; //just to get off the ) we just added popped := round(stackPop); expressionArrayLength := expressionArrayLength - 2; //this takes two away from the current expression array length because two brackets have been removed from the array // Pop the operators within the brackets to the end of the RPN array. while (popped <> 40) do begin inc(RPNcount); RPNVariablisedExpressionArray[RPNcount] := popped; popped := round(stackPop); end; end; end; end; //Pop any remaining operators on the stack to the RPN array if (indexOfTopOfStack > 0) then begin for i := 1 to indexOfTopOfStack do begin inc(RPNcount); popped := round(stackPop); RPNVariablisedExpressionArray[RPNcount] := popped; end; end; write('In Reverse Polish Notation: '); for i := 1 to expressionArrayLength do begin write(chr(RPNVariablisedExpressionArray[i])); end; writeln; {Evaluate the RPN. Before the operators are used, the stack will contain numbers pushed with the line of code in the else clause below: stackPush(VariableStorageArray[currentChrByte - 96]);} indexOfTopOfStack := 0; for i:= 1 to expressionArrayLength do begin currentChrByte := RPNVariablisedExpressionArray[i]; case currentChrByte of 43 : begin tempReal1 := stackPop; tempReal2 := stackPop; stackPush(tempReal1 + tempReal2); end; 42 : begin tempReal1 := stackPop; tempReal2 := stackPop; tempReal2 := tempReal2 * tempReal1; stackPush(tempReal2); end; 45 : begin tempReal1 := stackPop; tempReal2 := stackPop; stackPush(tempReal2 - tempReal1); end; 47 : begin tempReal1 := stackPop; tempReal2 := stackPop; tempReal2 := tempReal2 / tempReal1; stackPush(tempReal2); end; else begin //Push the number represented by its lower case letter to the stack stackPush(VariableStorageArray[currentChrByte - 96]); end; end; end; finalAnswer := stackPop; write('Final Answer: '); writeln(finalAnswer : 1 : 3); readln; end.

## Remarks

Can you follow the logic of this program?