如何使用栈来评估逆波兰表达式

Question

这个后缀表达式能被评估吗？

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

- Zeeshan Asif

---

是的，你最终会在堆栈上得到[7 2 8]（从底部到顶部）- 表达式没有完全折叠，因为没有足够的运算符。您可以使用dc来检查：6 2 3 + - 3 8 2 / + * 2 5 3 + f评估您的RPN表达式并转储堆栈（f）。 （但这不是一个真正的“编程”问题，除非您正在询问代码...） - nneonneo

我投票关闭此问题，因为它与编程无关 - 只涉及对特定的RPN表达式的评估。 - nneonneo

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

- Yakov Galka

Answer 2

只需遍历整个数组并执行以下操作:

• push 遇到的每个数字到栈中
• 如果遇到 操作符号 - 从栈中弹出两个数字并计算操作符
• push 操作结果回到栈中

就是这样。时间复杂度为线性，O(n)，空间复杂度为线性，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)来改善这一点！ 在这里阅读有关该算法的更多信息。

- sol0mka