了解反向波兰表示法，用于家庭作业? [英] Understanding Reverse Polish Notation, for homework assignment?

问题描述

作为家庭作业的一部分，我被要求用 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

• 一种接受输入的方式，例如来自控制台的输入
• 一种标记化输入的方法(对于你正在做的事情，打破空白是可能足够了)
• 堆栈，用于存储值(操作数)(例如 3 和 4在上面)
• 操作字典

• 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 stack
• 4: It's a value, push it on the stack
• 2: 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 stack
• 9: 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

这篇关于了解反向波兰表示法，用于家庭作业?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！