[C++知识库]C语言栈的应用——中缀表达式转后缀表达式

算法思路

将a+b+(c-d)*e转换为后缀表达式，从左向右读取，读取到数字的时候（这里例子里面是字母），就将数字直接添加到后缀表达式中；遇到操作符时，将读取到的操作符与栈中元素进行对比，如果读取的操作符的优先级小于等于栈中的操作符，就将栈中的操作符弹出并添加到后缀表达式中，并且将读取的操作符压入栈中，否则直接将操作符压入栈中。

具体转化过程

1. 读取到数字a，将数字a添加到postfixList的末端；此时postfixList=['a'](postfixList表示后缀表达式)

2. 读取到操作符+，此时操作符栈op为空，直接将操作符压入栈中；此时栈op=['+'](为了方便演示，使用数组表示栈)

3. 读取到数字b，将数字b添加到postfixList的末端；此时postfixList=['a','b']

4. 读取到操作符'+'，因为只有'('比'+','-'优先级小，所以将栈op中除了'('所有操作符弹出，此时postfixList=['a','b','+']，栈op=['+']

5. 读取到操作符'('，优先级最小，直接压入栈中，此时postfixList=['a','b','+']，栈op=['+','(']

6. 读取到数字c，将数字c添加到postfixList的末端，此时postfixList=['a','b','+','c']

7. 读取到操作符'-'，因为op栈顶元素'('优先级较小，直接将'-'压入栈中，此时栈op=['+','(','-']

8. 读取到数字d，将数字d添加到postfixList的末端，此时postfixList=['a','b','+','c','d']

9. 读取到操作符')'，将栈中'('上面所有的元素全部弹出并添加到postfixList末端，并将'('删除，此时postfixList=['a','b','+','c','d','-']，栈op=['+']

10. 读取到操作符'*'，因为'*'比栈顶元素'+'优先级高，所以直接压入栈中，此时栈op=['+','*']

11. 读取到数字e，将数字e添加到postfixList的末端，此时postfixList=['a','b','+','c','d','-','e']

12. 中缀表达式全部读取完毕，如果栈op未空，将栈op的所有元素弹出并添加到postfisList末尾，最后输出postfixList即为转化完成的后缀表达式，此时postfixList=['a','b','+','c','d','-','e','*','+']

13. 所以中缀表达式a+b+(c-d)*e转化为后缀表达式为ab+cd-e*+

代码实现

// 中缀表达式转后缀表达式
void InfixToPostfix()
{
    int length, i, j=0;  // 定义表达式长度
    LiStack op;    // 定义op操作符栈
    op = initStack();

    char infixList[100],postfixList[100] = {0};;  // infixList保存中缀表达式,初始化postfixList，postfixList保存操作完之后的后缀表达式

    printf("请输入中缀表达式:\n");
    scanf("%s", infixList);
    getchar();
    length = (int) strlen(infixList);

    // 主循环
    for (i = 0; i < length; i++)
    {
        if (isdigit(infixList[i]))      // 判断是否为数字，isdigit函数包含在"ctype.h"头文件中，如果为数字则返回1，否则返回0
        {
            postfixList[j++] = infixList[i];    // 如果是数字，将数字直接添加到后缀表达式末尾
        }
        else
        {
            if (infixList[i] == '(')   // 如果是左括号，直接压入栈中
            {
                push(op, infixList[i]);
            }
            else if (infixList[i] == ')')    // 如果是右括号，将左括号前的所有操作符添加到后缀表达式末尾
            {
                while (top(op) != '(')  // 如果栈顶不是左括号，将栈顶元素添加到后缀表达式末尾
                {
                    postfixList[j++] = (char)pop(op);
                }
                pop(op);    // 弹出左括号
            }
            else    // 如果是其他操作符，则按照优先级进行
                    // 若读取的操作符优先级等于或低于当前栈顶元素，将栈顶元素弹出添加到后缀表达式末尾
            {
                if (infixList[i] == '+' || infixList[i] == '-')     // +或-优先级最小
                {
                    if (stackEmpty(op))      // 如果栈空，直接压入
                    {
                        push(op, infixList[i]);
                    }
                    else    // 栈中除了左括号'('其他的都弹出
                    {
                        while (!stackEmpty(op) && ((char)top(op) != '('))
                        {
                            postfixList[j++] = (char) pop(op);
                        }
                        push(op, infixList[i]);     // 最后将+或-压入栈中
                    }
                }
                else    // *或/，如果栈顶为+或-，压入栈中
                {
                    if ((char)top (op) == '+' || (char)top (op) == '-' || (char)top (op) == '(')
                    {
                        push(op, infixList[i]);
                    }
                    else
                    {
                        postfixList[j++] = (char) pop(op);
                        push(op, infixList[i]);

                    }
                }
            }
        }
    }

    while (!stackEmpty(op))
    {
        postfixList[j++] = (char)pop(op);
    }

    printf("%s\n", postfixList);
}