# 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.

The program converts the input string to an array of string, ExpressionArray. The binary operators /, *, - and + and the brackets ( and ) are stored as strings of length 1. The length of each number string is allowed to build up as necessary with this line of code:
`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).

A stack is used to hold operators in the conversion from infix to RPN:
1. If the incoming symbol is a variable or constant, copy it to the RPN output.
2. 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.
3. 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.
4. The left bracket, (, goes on top of the operator stack and remains there until released by ).
5. 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.
6. When the end of the input stream is reached, any operators remaining on the stack are released to the RPN stream, completing the conversion.
In the following algorithm for the evaluation of an RPN expression, the term 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:
1. If the scanned symbol is a variable or constant, push its value to the stack and scan the next symbol.
2. 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.
3. 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;
{

use this file except in compliance with the License, as described at
}
{\$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;
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): ');
//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;
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);
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;
/////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;