这个后缀表达式能被评估吗?
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
遇到的每个数字到栈中操作符号
- 从栈中弹出两个数字并计算操作符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)来改善这一点! 在这里阅读有关该算法的更多信息。
dc
来检查:6 2 3 + - 3 8 2 / + * 2 5 3 + f
评估您的RPN表达式并转储堆栈(f
)。 (但这不是一个真正的“编程”问题,除非您正在询问代码...) - nneonneo