【2023王道数据结构】【栈的应用】中缀表达式转成后缀表达式C、C++完整实现（可直接运行）

~~~笔锋至此又怎能平淡而终，故事开始便不承认普通✌✌✌

如果需要完整代码可以关注下方公众号，后台回复“代码”即可获取，阿光期待着您的光临~

✌ 题目及题解持续更新中
【2023王道数据结构目录】课后算法设计题C、C++代码实现完整版大全

题目： 栈的应用——中缀表达式转成后缀表达式

解题思路：

>遇到操作数，将其直接加入后缀表达式
>遇到界限符：如果是(，直接入栈
           如果是)，则依次弹出栈内运算符将其加入后缀表达式直到遇到左括号
>遇到运算符，依次弹出优先级高于或等于当前运算符的所有运算符，并加入后缀表达式
直到遇到左括号或者是栈空
>将栈中剩余运算符依次弹出，并加入后缀表达式

代码实现：

#include 
using namespace std;
#define MAXSIZE 100

//定义栈
typedef struct
{
    char data[MAXSIZE];
    int top1 = -1;
} Stack;

//判断栈是否为空
bool StackEmpty(Stack s)
{
    if (s.top1 == -1)
    {
        return true;
    }
    return false;
}

//判断栈是否溢出
bool StackOverflow(Stack s)
{
    if (s.top1 >= MAXSIZE)
    {
        return true;
    }
    return false;
}

//压栈
void Push(Stack &s, char x)
{
    if (!StackOverflow(s))
    {
        s.data[++s.top1] = x;
    }
    else
    {
        cout << "当前栈已满" << endl;
    }
}

//弹栈
char Pop(Stack &s)
{

    if (StackEmpty(s))
    {
        // cout << "当前栈已空" << endl;
        return '';
    }
    else
    {
        return s.data[s.top1--];
    }
}

//将中缀表达式转为后缀表达式
string InfixToSuffix(string infix)
{
    Stack s;
    string suffix = "";
    char op;

    for (int i = 0; i < infix.length(); i++)
    {
        //遇到操作数直接加入后缀表达式
        if (infix[i] >= 'A' && infix[i] <= 'Z')
        {
            suffix += infix[i];
        }
        //碰到左括号直接入栈
        else if (infix[i] == '(')
        {
            Push(s, infix[i]);
        }
        //碰到右括号依次弹出所有运算符将其加入后缀表达式
        else if (infix[i] == ')')
        {
            while (!StackEmpty(s))
            {
                op = Pop(s);
                if (op != '(')
                {
                    suffix += op;
                }
                else
                {
                    break;
                }
            }
        }

        else
        {
            //如果是乘号或者除号只弹出乘号或者除号
            if (infix[i] == '*' || infix[i] == '/')
            {

                while (!StackEmpty(s))
                {
                    op = Pop(s);
                    if (op == '(')
                    {
                        break;
                    }
                    else
                    {
                        //碰到低级运算符弹出再压回去
                        if (op == '+' || op == '-')
                        {
                            Push(s, op);
                            break;
                        }
                        else
                        {
                            suffix += op;
                        }
                    }
                }
            }
            //碰到+-运算符则将其所有运算符弹出
            else if (infix[i] == '+' || infix[i] == '-')
            {
                while (!StackEmpty(s))
                {
                    op = Pop(s);
                    if (op == '(')
                    {
                        break;
                    }
                    else
                    {
                        suffix += op;
                    }
                }
            }
            //将当前运算符压入栈中
            Push(s, infix[i]);
        }
    }

    //将栈中剩余运算符依次弹出
    while (!StackEmpty(s))
    {
        suffix += Pop(s);
    }

    return suffix;
}

int main()
{
    string infix = "A+B*(C-D)-E/F";
    cout << InfixToSuffix(infix);
}