c++ - 使用链表堆栈中缀到 Postfix 转换器

Question

编写一个程序，使用链表堆栈将中缀表示法中的方程式转换为后缀表示法。程序的堆栈部分是它自己的类，在它自己的头文件中，并且正确实现(能够编译和运行我教授提供的测试主程序)。我目前正在研究将中缀字符串转换为继承类中的后缀字符串的实际函数。我有以下代码，自从我得到奇怪的输出后，我认为它在某处错误地完成了调车场算法。

template <class myType>
void infixToPostfix<myType>::convertToPostfix()
{
    linkedStack<char> newS; //creating a new char stack
    string output; //creating the postfix output string

    for(int i = 0; i < infx.length(); i++) //cycle through the entire string
    {
        if (isgraph(infx[i])) //skip spaces
        {
            if (isalpha(infx[i])) //if the char is a letter (caps or uncaps)
            {
                output += infx[i]; //append it to output
            }
            else
            {
                if (newS.isEmptyStack()) newS.push(infx[i]);
                else if (precedence(infx[i], newS.top()) //check if the current char has higher precedence than the top of the stack, or if the stack is empty
                {
                    newS.push(infx[i]); //push the current char onto the stack
                }
                else if (infx[i] == ')') //check if the current char is a closing paren
                {
                    for(;;)
                    {
                        if (newS.isEmptyStack()) break;
                        if (newS.top() != '(') //check if the top of the stack isn't an open paren
                        {
                            output += newS.top(); //append the top of the stack to the output
                            newS.pop(); //pop the top of the stack off
                        }
                        else //the top of the stack is a (
                        {
                            newS.pop(); //pop the ( off the stack
                            break; //break out of the for loop
                        }
                    }
                }
                else //the current char doesn't have higher precedence than the top of the stack
                {
                    output += newS.top(); //append to the top of the stack to output
                    newS.pop(); //pop off the top of the stack
                    newS.push(infx[i]); //put the current char onto the top of the stack
                }
            }
        }
    }

    while (!newS.isEmptyStack()) //not sure if this works, assuming we're at the end of the line at this point, and if there's anything on the stack we need to append it to the output
    {
        output += newS.top();
        newS.pop();
    }

    pfx = output; //setting pfx to the output (pfx is the class variable for the postfix output)

}

我显示后缀字符串的函数如下

template <class myType>
void infixToPostfix<myType>::showPostfix()
{
    cout << "Postfix Expression: " << pfx << endl;
}

运行程序时得到以下输出。

silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$ ./a.out testinput1.txt
Infix Expression: A + B - C
-ostfix Expression: AB+C
Infix Expression: A + B * C
*+stfix Expression: ABC
Infix Expression: A * B + C / D
/+stfix Expression: AB*CD
Infix Expression: (A + B) * C
*+(tfix Expression: AB)C
Infix Expression: A * (B + C) / D
/+(tfix Expression: A*BC)D
Infix Expression: (A + B) * (C - D)
-(+(fix Expression: AB)*CD)
Infix Expression: A * (B + C / D)
/+(tfix Expression: A*BCD)
Infix Expression: A + ((B + C) * (E - F) - G) / (H - I)
-(--(+( Expression: A+(BC)*EF)G)/HI)
silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$ 

老实说，我不明白为什么后缀表达式的奇数位会被推到我的 cout 中的字符串上。任何提示/帮助？

编辑:按照 ymett 的建议进行更改后，我的输出如下。我现在正试图找出我在尝试处理括号时出错的地方。

silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$ ./a.out testinput1.txt
Infix Expression: A + B - C
Postfix Expression: AB+C-
Infix Expression: A + B * C
Postfix Expression: ABC*+
Infix Expression: A * B + C / D
Postfix Expression: AB*CD/+
Infix Expression: (A + B) * C
Postfix Expression: AB)C*+(
Infix Expression: A * (B + C) / D
Postfix Expression: A*BC)D/+(
Infix Expression: (A + B) * (C - D)
Postfix Expression: AB)*CD)-(+(
Infix Expression: A * (B + C / D)
Postfix Expression: A*BCD)/+(
Infix Expression: A + ((B + C) * (E - F) - G) / (H - I)
Postfix Expression: A+(BC)*EF)G)/HI)-(--(+(
silverbox@silverbox-VirtualBox:~/Dropbox/CS202/ass13$ 

Answer 1

你还没有展示如何infx已填充，但它似乎在末尾有一个回车符 (CR, '\r', 0x0d, 13)。

您的情况infx[i] != ' '应替换为检查任何空白字符的条件，即 !isblank(infx[i]) .更好的是，不是检查您不需要的字符，而是检查您确实需要的字符；如果您没有列表，请使用 isgraph(infx[i]) (具有可见表示的任何字符，即不是控制字符或空格)。

条件infx[i] >= 65 && infx[i] <= 122也不好首先你应该使用字 rune 字而不是数字，即infx[i] >= 'A' && infx[i] <= 'z' .其次，您在 'Z' 之间包含了字符和 'a'这不是字母，所以它应该是(infx[i] >= 'A' && infx[i] <= 'Z') || (infx[i] >= 'a' && infx[i] <= 'z') .此外，您假设字母在字符集中是连续的，这对于 ASCII 是正确的，但对于所有字符集并非如此(尽管也许我们不必担心这一点)。更好地使用语言为您提供的工具，并编写 isalpha(infx[i]) .