如何評估使用堆棧的逆波蘭表示法

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

簡單地重複通整個陣列和：

• push每個number您滿足堆棧
• 如果你遇到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）！閱讀更多關於算法here。