中缀到后缀转换器，不输出正确答案

Question

我得到了一个学校项目，其中提供了以下信息：

for i=1 to m
if c_i is an operand: Transfer c_i to output.
if c_i is a left parentheses: Push c_i to tmp.
if c_i is a right parentheses: Pop elements from tmp and transfer
them to output until a left-parentheses
is met. Pop left-parentheses.
if c_i is an operator: Let the top tmp element be t. Pop and
transfer elements from tmp to output
until:
p(t) < p(c_i) or
t is a left-parentheses or
tmp is empty.
Push c_i to tmp.
Transfer the remaining elements in tmp to output.

我一直在执行这些步骤，但我的输出只在某些时候正确。我想我在 if 运算符语句周围的某个地方想错了。我一直在调试 2 天，我就是找不到解决方案。

如果有人愿意检查我的代码，我将非常高兴。 operatorCheck 函数是为解决这个问题而创建的：“我们使用子程序 p 来指定运算符的优先级：

p(+) = 0,
p(−) = 0, p(∗) = 1, p(/) = 1

。这意味着加法和减法有与乘法和除法相比优先级较低。"

代码：http://pastebin.com/TA7UGiGc

谢谢！

Answer 1

Marco，在你的代码中，第 42 行

while (tmp.length() > 0 && !(operatorCheck(t) > operatorCheck(character)) && t != '(')

您必须将 > 更改为 <

算法中，退出条件为

tmp.length()==0 || p(t) < p(c_i) || t=='('

因为它有一段时间你必须否定它

!(tmp.length()==0 || p(t) < p(c_i) || t=='(')
===
(tmp.length()>0 && p(t) >= p(c_i) && t!='(')
=== (to write it with ! as you did)
(tmp.length()>0 && !(p(t) < p(c_i)) && t!='(')

除此之外，Dante 关于堆栈的使用是正确的。如果你想避免自动装箱问题，你可以为 char

创建你自己的原始堆栈 class

Answer 2

您正在循环并从 tmp 中删除第一个字母，而没有在 while 循环中获取要与之比较的下一个字母，因此您需要在 while 循环中获取一个新字符。

子字符串也从 tmp 中删除了错误的字符，它应该保留除第一个字母以外的所有字符，这是通过 tmp.substring(1, tmp.length())

完成的

我已经修复了下面的代码块：

else if (character == '+' || character == '-' || character == '*' || character == '/'){
    while (true) {
        char t = tmp.length() > 0 ? tmp.charAt(0): ' ';
        if (operatorCheck(t) < operatorCheck(character) || t == '(' || tmp.length() < 0) {
            break;
        }

        output += t;
        tmp = tmp.substring(1, tmp.length());
    }
    tmp = character + tmp;
}

中缀到后缀转换器，不输出正确答案

infix to postfix converter, not outputting right answer

java

rpn

converter

infix-notation