问题描述
作为家庭作业的一部分,我被要求用 C 语言编写一个简单的逆波兰符号计算器.我很难理解 RPN.你能帮我理解反向波兰表示法吗?此外,我们将不胜感激任何有关如何解决此问题的提示.
I have been asked to write a simple Reverse Polish Notation calculator in C as part of a homework assignment. I'm having difficulty understanding RPN. Can you please help me understand Reverse Polish Notation? Also, any tips on how to approach this problem would be greatly appreciated.
推荐答案
Reverse Polish Notation 是一种编写表达式的特定方式,首先编写值,然后编写要执行的操作.例如,要将数字 3 和 4 相加,您可以编写 3 4 +
.
Reverse Polish Notation is a specific way of writing expressions where first you write the values, then the operation you want to perform. So for instance, to add the numbers 3 and 4 you'd write 3 4 +
.
因此要编写 RPN 计算器,您需要
So to write an RPN calculator you'll need
- A means of accepting input, such as from the console
- A means of tokenizing the input (for what you're doing, breaking on whitespace is probably sufficient)
- A stack for storing values (operands) (such as the 3 and 4 in the above)
- A dictionary of operations
然后循环本质上变成:
while (there's a token available) {
token = get_the_token
if (token is known operator) {
get the number of values from stack this operation requires (usually two); fail if stack doesn't have enough
perform operation on values
push result on the stack
}
else if (token is valid value) {
push it on the stack
}
else {
show error: invalid input
}
}
show result remaining on stack
您可以理解为什么 RPN 使编写计算器变得相当容易:您不必担心在它们所操作的值之间使用运算符,并且您不需要像使用更常见的 中缀 符号形式.例如,我们用中缀表示法写 (10 + (4 * 2))/9
,我们用 RPN 写 10 4 2 * + 9/
.您的计算器会像这样处理这些标记:
You can see why RPN makes writing a calcuator fairly easy: You don't have to worry about having operators between the values they operate on, and you don't need parentheses for grouping as you do with the more common infix form of notation. For instance, where we'd write (10 + (4 * 2)) / 9
in infix notation, we'd write 10 4 2 * + 9 /
in RPN. Your calculator would process those tokens like this:
10
:是一个值,入栈4
:是一个值,入栈2
:是一个值,入栈*
:它是一个运算符,将 2 和 4 从堆栈中弹出并相乘 (4 * 2
);将结果 (8) 压入堆栈+
:它是一个操作符,将8和10从堆栈中弹出并相加(10 + 8
);将结果 (18) 压入堆栈9
:是一个值,入栈/
:是一个操作符,将9和18从栈中弹出并相除(18/9
);将结果(2)压入栈中(注意栈顶的值 9,在本例中 —是除数,它下面的下一个值 18 —是被除数)- 输入结束,显示堆栈中的值:
2
10
: It's a value, push it on the stack4
: It's a value, push it on the stack2
: It's a value, push it on the stack*
: It's an operator, pop 2 and 4 off the stack and multiply them (4 * 2
); push the result (8) on the stack+
: It's an operator, pop 8 and 10 off the stack and add them (10 + 8
); push the result (18) on the stack9
: It's a value, push it on the stack/
: It's an operator, pop 9 and 18 off the stack and divide them (18 / 9
); push the result (2) on the stack (note that the value at the top of the stack — 9, in this case — is the divisor, the next value under it — 18 — is the dividend)- End of input, show the value(s) on the stack:
2
这篇关于了解反向波兰表示法,用于家庭作业?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!