評価方法スタックを使用した逆ポーランド表記

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

だけで、アレイ全体を通して反復して：あなたはoperation token満たしている場合、あなたは、スタック

に応える

• push各number - 操作
• にスタックからpop 2つの数値を、評価を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の詳細については、こちらをご覧ください。