如何使用堆栈评估反向抛光表示法

Question

可以评估此​​后缀表达式吗？

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

Answer 1

是的,它可以.

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

Answer 2

只需遍历整个数组并：

• pushnumber你在堆栈中遇到的每一个
• 如果您遇到operation token-pop堆栈中的两个数字并评估操作
• push 你的操作结果回到堆栈

就是这样。这将是linear, O(n)时间和linear, O(n)空间的复杂性，因为我们使用堆栈来存储数字。使用堆栈( 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();
}

但是您可以通过使用常数空间 O(1) 来改进它！在此处阅读有关该算法的更多信息。