CODEWITHSUNDEEP
algorithmstackpostfix-notationrpn
Zeeshan Asif
Zeeshan Asif

Reputation: 61

How to evaluate Reverse polish notation using stacks

Can this postfix expression can be evaluated?

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

Upvotes: 6

Views: 12885

Answers (2)

sol0mka
sol0mka

Reputation: 1796

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.

Upvotes: 5

Yakov Galka
Yakov Galka

Reputation: 72529

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

Upvotes: 10

Related Questions