How to evaluate Reverse polish notation using stacks

Question

Can this postfix expression can be evaluated?

6 2 3 + - 3 8 2 / + * 2 5 3 +

Yes, and you end up with [7 2 8] on your stack (bottom to top) - the expression doesn't fully collapse since there's not enough operators. You can use `dc` to check this: `6 2 3 + - 3 8 2 / + * 2 5 3 + f` evaluates your RPN expression and dumps the stack (`f`). (But this isn't really a _programming_ question unless you are asking about code...) — nneonneo, Oct 30 '16 at 13:58
I'm voting to close this question as off-topic because it's not about programming - only about the evaluation of a _particular_ RPN expression. — nneonneo, Oct 30 '16 at 13:58

score 10 · Answer 1 · answered Oct 30 '16 at 13:59

10

Yes, it can.

S = new empty stack
while not eof
    t = read token
    if t is a binary operator
        y = pop(S)
        x = pop(S)
        push(S, t(x, y))
    else
        push(S, t)
print the contents of the stack S

answered Oct 30 '16 at 13:59

Yakov Galka

70,775
16
139
220

score 5 · Answer 2 · answered Nov 13 '16 at 05:24

Simply iterate thru entire array and:

push each number that you meet to the stack
if you meet operation token - pop two numbers from the stack and evaluate the operation
push the result of your operation back to the stack

That's it. Complexity for this will be linear, O(n) for time and linear, O(n) for space because we use the stack to store the numbers. The entire code using stack (JavaScript):

/*
  Function to perform operation with two numbers.
  @param {String} Operation type.
  @param {Number} Number 1.
  @param {Number} Number 2.
  @returns {Number} Result of performing the operation.
*/
var performOperation = function performOperation(operation, num1, num2) {
    switch (operation) {
        case '+': return num1 + num2;
        case '-': return num1 - num2;
        case '*': return ~~(num1 * num2);
        case '/': return ~~(num1 / num2);
        default: console.error('Unknown operation: ', operation);
    }
};
/*
  Function to check if variable holds an operation type.
  @param {Any} Token.
  @returns {Boolean} If token is string with operation type.
*/
var isOperation = function isNumber(token) {
    // map of supported operations
    var map = {
        '+': true,
        '-': true,
        '*': true,
        '/': true
    }
    return !!map[token];
};

var evaluatePolishNotation = function evaluatePolishNotation(tokens) {
  var stack = [];
  for (var i = 0; i < tokens.length; i++) {
    var token = tokens[i];
    if (isOperation(token)) {
      var number1 = stack.pop();
      var number2 = stack.pop();
      stack.push( performOperation(token, number2, number1) );
    } else {
      stack.push( parseInt(tokens[i], 10) );
    }
  }
  return stack.pop();
}

But you can improve that by using a constant space O(1)! Read more about the algorithm here.

How to evaluate Reverse polish notation using stacks

2 Answers2