RPN evaluation

There is a well know expression notation that appears often in computer science called RPN (reverse polish notation).  HP used this notation as is input format in their calculators for many years.  Suppose that you would like to evaluate the expression 2+3. In most calculators you would type 2 then + then 3 then =   to obtain the result 5.  On the other hand in an HP calculator you would type 2 enter 3 enter +  then =.  In other words you enter the two operands and then perform the add.   We normally write this as 2 3 + =.  Suppose we would like to calculate (5+4)*7 =.  Here the rpn would be 5 4 + 7 * =.  The simplest way to visualize this (an execute it) is by using a stack.  The rules are simple.

  1. Process from left to right
  2. If you encounter an integer push it on the stack
  3. if you encounter an operand then pop the top two integers from the stack, apply the operation to these two values and push the result on the stack.
  4. if you encounter the ‘=’ then the stack should have only one value on it and it is then removed from the stack and printed.  This is the final result.

Here is an example function that would perform the above operation if given a string in RPN format.

int eval(string cmd) {// String is RPN  ie 4 6 8 + * =
  stack<int> stk;
  int a, b,pos=0,result;
  bool moreTokens = true;
  while (moreTokens) {// keep going until =
   // Grab next token
    while (cmd[pos] == ' ')pos++;//skip blanks
// if we see a number token then apply Horner's rule
    if (isdigit(cmd[pos])) {// get integer
        int s = 0;
        while (isdigit(cmd[pos])) {
        s = s * 10 + cmd[pos++]-48;
   }
   stk.push(s);// push the integer on the stack
 }
 else {// it is either an operand or an =
 switch(cmd[pos]){
 case '=':// hit the eval request
    result=stk.top();
    moreTokens = false;
    break;
 case '+':// perform and + operation
    a = stk.top(); stk.pop();
    b = stk.top(); stk.pop();
    stk.push(a + b); pos++;
    break;
  case '*':// perform a * operation
    a = stk.top(); stk.pop();
    b = stk.top(); stk.pop();
    stk.push(a*b); pos++;
   }
  }
 }
 return result;
}

As a side note , the users of HP calculators had to convert normal mathematical parenthesised notation (commonly called infix) to RPN (also called postfix) on the fly as they typed the expression into the calculator.  You may think that this would be complicated (it is) but most became so proficient that it soon became natural.  Also you probably have come to realize that there are no parenthesised in RPN!  Order of operations is naturally embedded in the notation.

Comments are closed.