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;
{
    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?

Programming - a skill for life!

Fourteen programs (with five web versions) including 3D-Driving, GASP and Knowledge by Peter Hearnshaw