在 C++ 中对 Postfix Converter 的中缀没有输出

Question

我创建了一个函数 infixToPostfix()，它将中缀表达式转换为后缀表达式。但是我的程序在运行上没有生成任何输出。请指出我程序中的错误。

代码：

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdlib>
using namespace std;

int isOperator(char x)
{
    return (x == '-' || x == '+' || x == '/' || x == '*');
}

int precedenceOfOperators(char x)
{
    if (x == '+' || x == '-')
    {
        return 1;
    }
    else if (x == '/' || x == '*')
    {
        return 2;
    }

    return 0;
}

char *infixToPostfix(char infix[])
{
    int i = 0, j = 0;
    stack<char> lobby;
    char *postfix = (char *)malloc((strlen(infix + 1)) * sizeof(char));
    while (infix[i] != '[=10=]')
    {
        if (!isOperator(infix[i]))
        {
            postfix[j] = infix[i];
            i++;
            j++;
        }
        else
        {
            if (!lobby.empty())
            {
                if (precedenceOfOperators(infix[i]) > precedenceOfOperators(lobby.top()))
                {
                    lobby.push(infix[i]);
                }
                else
                {
                    postfix[j] = lobby.top();
                    lobby.pop();
                    j++;
                }
            }
            else if (lobby.empty())
            {
                lobby.push(infix[i]);
            }
        }
    }
    while (!lobby.empty())
    {
        postfix[j] = lobby.top();
        lobby.pop();
        j++;
    }
    return postfix;
}

实施：

int main()
{
    char infix[] = {'a', '-', 'b', '+', 'c', '*', 'd'};
    char *postfix = infixToPostfix(infix);
    for (int j = 0; postfix[j] != '[=11=]'; j++)
    {
        cout << postfix[j];
    }
    return 0;
}

逻辑：

我创建了一个字符指针变量来保存我们的后缀表达式。现在，我们迭代我们的中缀表达式。如果我们收到一个操作数，我们将它连接到后缀变量。否则，如果遇到运算符，我们将继续执行以下步骤：

考虑运算符及其相对优先级（“/”和“*”的优先级高于“+”和“-”）。
如果堆栈为空或其最顶层运算符的相对优先级较低，则将此运算符-优先级对压入堆栈 'lobby'。
否则，继续从堆栈中弹出运算符 'lobby' 并将它们连接到后缀表达式，直到最顶层的运算符相对于当前运算符的优先级变弱。

如果到达 EOE，从堆栈中弹出每个元素 'lobby'，如果有的话，并将它们连接到后缀表达式。

Answer 1

您的代码超出了时间限制，因为它陷入了无限循环。您尚未更新 i variable- 这是循环的 else 部分中缀数组的索引，即当 infix[i] 是运算符时。即在这部分代码中

else
        {
            if (!lobby.empty())
            {
                if (precedenceOfOperators(infix[i]) > precedenceOfOperators(lobby.top()))
                {
                    lobby.push(infix[i]);
                }
                else
                {
                    postfix[j] = lobby.top();
                    lobby.pop();
                    j++;
                }
            }
            else if (lobby.empty())
            {
                lobby.push(infix[i]);
            }
        }

这是提供完美输出的更新代码。（我根据自己的方便做了一些小改动，你可以保持代码不变，并在 else 部分添加 i++）

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdlib>
using namespace std;

int isOperator(char x)
{
    return (x == '-' || x == '+' || x == '/' || x == '*');
}

int precedenceOfOperators(char x)
{
    if (x == '+' || x == '-')
    {
        return 1;
    }
    else if (x == '/' || x == '*')
    {
        return 2;
    }

    return 0;
}

string infixToPostfix(char infix[])
{
    int i = 0, j = 0;
    if(sizeof(infix)==0)
    {
        return "";
    }
    int n=sizeof(infix)/sizeof(infix[0]);
    stack<char> lobby;
    string postfix = "";
    while (i < n)
    {
        if (!isOperator(infix[i]))
        {   postfix=postfix+infix[i];
            i++;
            j++;
        }
        else
        {
            if (!lobby.empty())
            {
                if (precedenceOfOperators(infix[i]) > precedenceOfOperators(lobby.top()))
                {
                    lobby.push(infix[i]);
                }
                else
                {
                    postfix = postfix+lobby.top();
                    lobby.pop();
                    j++;
                }
            }
            else if (lobby.empty())
            {
                lobby.push(infix[i]);
            }
            i++;
        }
    }
    while (lobby.empty()==false)
    {
        postfix = postfix+lobby.top();
        lobby.pop();
        j++;
    }
    return postfix;
}
int main()
{
    char infix[] = {'a', '-', 'b', '+', 'c', '*', 'd'};
    string postfix = infixToPostfix(infix);
    for (int j = 0; j < postfix.size() ; j++)
    {
        cout << postfix[j];
    }
    return 0;
}

Answer 2

再次检查我的代码后，我还发现了其他一些逻辑错误。我找到了一种更好的方法，并重构了函数 infixToPostfix().
我没有将中缀表达式作为字符数组，而是将其作为字符串，类似地，后缀表达式也被视为字符串。

已更新infixToPostfix()：

string infixToPostfix(string infix)
{
    int i = 0;
    stack<char> lobby;
    string postfix;
    if (infix.size() == 0)
    {
        return "";
    }
    while (infix[i] != '[=10=]')
    {
        if (!isOperator(infix[i]))
        {
            postfix = postfix + infix[i];
            i++;
        }
        else
        {
            while (!lobby.empty() && precedenceOperator(infix[i]) <= precedenceOperator(lobby.top()))
            {
                postfix += lobby.top();
                lobby.pop();
            }
            lobby.push(infix[i]);
            i++;
        }
    }
    while (!lobby.empty())
    {
        postfix = postfix + lobby.top();
        lobby.pop();
    }
    return postfix;
}

并且如其他答案中所述，i variable 也应在 while 循环的 else 部分更新。

在 C++ 中对 Postfix Converter 的中缀没有输出

Infix to Postfix Converter in C++ gives no output

c++

stack

output

postfix-operator

infix-operator