How to evaluate Reverse polish notation using stacks

algorithm stack postfix-notation rpn

11,040

Solution 1

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

Solution 2

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.

11,040