2016-10-30 5 views
3

Можно ли оценить это постфиксное выражение?Как оценить Обозначение с обратной полярностью с использованием стеков

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

Да, и вы получите [7 2 8] в своем стеке (снизу вверх) - выражение не полностью разрушается, так как операторов недостаточно. Вы можете использовать 'dc', чтобы проверить это:' 6 2 3 + - 3 8 2/+ * 2 5 3 + f' оценивает ваше выражение RPN и выгружает стек ('f'). (Но это не вопрос _programming_, если вы не спрашиваете о коде ...) – nneonneo

+0

Я голосую, чтобы закрыть этот вопрос как вне темы, потому что речь идет не о программировании - только об оценке выражения _particular_ RPN. – nneonneo

ответ

4

Да, может.

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 
1

Просто итерацию через весь массив и:

  • 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.

 Смежные вопросы

  • Нет связанных вопросов^_^