【C语言中缀转后缀】

中缀表达式

• 我们把平常所用的标准四则运算的表达式叫做中缀表达式，所有的运算符号都在俩数字中间

后缀表达式

• 后缀表达式是栈的运用，利用数组模拟栈的先进后出的特点，对后缀表达式进行计算
• 后缀表达式：后缀表达式是一种不需要括号的后缀表达法，我么也把他称为逆波兰表达式，为什么叫后缀表达式？原因就是所有的符号都是要在运算数字的后面出现

为什么要用后缀表达式

• 计算器读取更方便，计算起来更方便
• 举例：9+(3-1)*3+10/2进行后缀表达式的运算得出结果 9 3 1 - 3 * + 10 2 / +

中缀转后缀

• 就以上述表达式为例子，将上述中缀表达式专为后缀
• 规则：从左到右遍历表达式的每个数字和符号，若是数字就输出（这里存放一个数组来将输出后的表达式放进去）成为后缀表达式的一员，若是符号，这里判断它与栈顶符号的优先级，是右括号或优先级不高于栈顶符号，则栈顶元素依次出栈并输出，并将当前的符号进栈，一直到输出完为止
• 上述的优先级是乘除大于加减，并且遇到右括号时候右括号是不进栈的
• 对于上述规则，我虚拟了一个存放操作符的栈
  
  
  
  
  
  

代码解析

• 定义运算优先级，对于计算机来说呀要让他准确的识别符号的优先级，我们设置一个Compare函数即可
• Compare
• 当遇到# 代表输入结束，返回0，遇到数字直接进入后缀表达式数组

/**
 中缀转后缀
 把输入的字符串分开来读取，根据优先级返回不同的数字，乘除最高，加减次之，括号最后，符号出栈的时候括号不进入后缀表达式的行列
 */
int Compare(char str1) {
    if (str1 == '#') {
        return 0;
    } else if (str1 == '+' || str1 == '-') {
        return 1;
    } else if (str1 == '*' || str1 == '/') {
        return 2;
    } else if (str1 == '(' || str1 == ')') {
        return 0;
    }
    else {
        return -1; //数字
    }
}

• 后缀栈和操作符栈，虚拟栈模拟栈顶指针top = -1

 char outPutStack[100] = {0};//结果栈
    int outPuttop = -1;//模拟栈顶指针
    char sympolStack[100] = {0};//中间栈（只存放字符）
    int sympolTop = -1;//模拟栈顶指针

• 输入字符串

char inputStr[100] = {0};//输入数组
scanf("%s", inputStr);
    int strLength = (int)strlen(inputStr);

• 主要算法代码的实现

 /**
        循环读取输入的表达式，进行入栈或者出栈
     */
    for (int i = 0; i < strLength;) {
        if (Compare(inputStr[i]) == -1) {
            outPutStack[++outPuttop] = inputStr[i++]; // 数字直接入后缀栈，i++表达先i后++
        } else if (inputStr[i] == '(') {
            sympolStack[++sympolTop] = inputStr[i++]; // 左括号先入表达式栈
        } else if (inputStr[i] == ')') {
            // 遇到右括号直接从符号栈里面开始找，Copmare函数，直接把括号的符号进入后缀栈，括号不进栈
            while (Compare(sympolStack[sympolTop]) != 0) {
                outPutStack[++outPuttop] = sympolStack[sympolTop--];
            }
            sympolTop--;//括号不入栈，直接把sympoltop--即可
            i++;
        } else { //遇到操作符
            // 根据规则。输入数组的操作符优先级大于等于操作栈顶元素的优先级的时候该运算符入栈
            if (sympolTop == -1 || Compare(sympolStack[sympolTop]) < Compare(inputStr[i])) {
                sympolStack[++sympolTop] = inputStr[i++];
            } else {
               // 若字符串中的操作符优先级小于或等于操作符栈顶操作符的优先级，就将操作符栈的栈顶元素弹出压入结果栈中，并且字符串中的位置不变，直到操作符栈为空或遇到高优先级的操作符
                outPutStack[++outPuttop] = sympolStack[sympolTop--];
            }
            if (inputStr[i] == '#') {
                while (sympolTop != -1) {
                    outPutStack[++outPuttop] = sympolStack[sympolTop--];
                }
                break;
            }
        }
    }
    char endStack[outPuttop + 1];
    for (int i = 0; i < outPuttop +1; i++) {
        endStack[i] = outPutStack[i];
        printf("%c", outPutStack[i]);
    }
    return 0;
}

总结

• 中缀转后缀最主要的是强调算法过程，什么时候入栈什么时候出栈，记住符号的优先级，尤其注意top指针的位置，最后还需要查看符号栈是不是清空了，之前出现了少一个符号的问题