Можно ли оценить это постфиксное выражение?Как оценить Обозначение с обратной полярностью с использованием стеков
6 2 3 + - 3 8 2/+ * 2 5 3 +
Можно ли оценить это постфиксное выражение?Как оценить Обозначение с обратной полярностью с использованием стеков
6 2 3 + - 3 8 2/+ * 2 5 3 +
Да, может.
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
Просто итерацию через весь массив и:
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.
Да, и вы получите [7 2 8] в своем стеке (снизу вверх) - выражение не полностью разрушается, так как операторов недостаточно. Вы можете использовать 'dc', чтобы проверить это:' 6 2 3 + - 3 8 2/+ * 2 5 3 + f' оценивает ваше выражение RPN и выгружает стек ('f'). (Но это не вопрос _programming_, если вы не спрашиваете о коде ...) – nneonneo
Я голосую, чтобы закрыть этот вопрос как вне темы, потому что речь идет не о программировании - только об оценке выражения _particular_ RPN. – nneonneo