了解反向波兰表示法,作业作业？

Question

我被要求在C中写一个简单的反向波兰表示法计算器作为家庭作业的一部分.我很难理解RPN.你能帮我理解反波兰表示法吗？此外,非常感谢有关如何处理此问题的任何提示.

Answer 1

反向波兰表示法是一种编写表达式的特定方法,首先编写值,然后执行要执行的操作.例如,要添加数字3和4,你要写3 4 +.

所以要写一个你需要的RPN计算器

• 接受输入的方法,例如从控制台接收输入
• 一种标记输入的方法(对于你正在做的事情,在空白处打破可能就足够了)
• 甲堆栈,用于存储的值(操作数)(在上述诸如3和4)
• 操作词典

然后循环变为,实质上:

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中缀表示法编写,我们10 4 2 * + 9 /用RPN 编写.你的计算器会像这样处理这些令牌:

• 10:这是一个值,将它推到堆栈上
• 4:这是一个值,将它推到堆栈上
• 2:这是一个值,将它推到堆栈上
• *:它是一个运算符,从堆栈中弹出2和4并将它们相乘(4 * 2); 将结果(8)推到堆栈上
• +:它是一个操作符,从堆栈弹出8和10并添加它们(10 + 8); 将结果(18)推到堆栈上
• 9:这是一个值,将它推到堆栈上
• /:它是一个操作符,从堆栈中弹出9和18并将它们分开(18 / 9); 将结果(2)推到堆栈上(注意堆栈顶部的值 - 在这种情况下为9 - 是除数,其下的下一个值 - 18 - 是被除数)
• 输入结束,显示堆栈上的值: 2