(22)王道数据结构-栈在表达式求值中应用

表达式

中缀表达式

运算符在两个操作数中间
例如:
a + b
a + b - c
a + b - c*d

后缀表达式

运算符在两个操作数后面，最后出现的操作数先被运算，与栈十分吻合
例如:
ab +
ab + c -
ab + cd*-

前缀表达式

运算符在两个操作数前面
例如:
+ab
-+abc
-+ab*cd

中缀转后缀

计算方法

①确定中缀表达式中各个运算符的运算顺序
②选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
③如果还有新运算符没被处理，就继续②

计算案例

中缀:((15÷(7-(1+1))x3)-(2+(1+1))
运算符次序：③ ② ① ④ ⑦ ⑥ ⑤
**后缀:**15 7 1 1 + - ÷ 3 x 2 1 1 + + -
运算符次序: ① ② ③ ④ ⑤ ⑥ ⑦

注意:**运算顺序如果不唯一，对应的后缀表达式也不唯一
**中缀:**A + Bx(C-D) - E/F
运算符次序：③ ② ① ⑤ ④
运算符次序：⑤ ③ ② ④ ①
**后缀:
表达式一：A B C D - x + E F / -
运算符次序：① ② ③ ④ ⑤
表达式二：A B C D - x E F / -
运算符次序：② ③ ① ④ ⑤
为了保证计算机中运算结果唯一，有左优先原则

手算后缀

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算合体为一个操作数

机算后缀

①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①，否则执行③，先出栈的是“右操作数”
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

机算前缀

①从右往左扫描到下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①，否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①，先出栈的是“左操作数”

机转后缀

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左往右处理各个元素，直到末尾。可能遇到三个情况：
①遇到操作数。直接加入后缀表达式
②遇到界限符。遇到“(”直接压入栈，遇到”)”则依次弹出栈内运算符并加入后缀表达式，直到弹出”(“为止。注意：“(”不加入后缀表达式
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈
处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式

实现代码

参考原文

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define  MAX_LEN 30
#define  MAX 100
//栈的数组实现
typedef struct {
    int data[MAX_LEN];
    int top;
}Stack;
//为栈分配空间
Stack *Createstack() {
    Stack *p;
    p = (Stack *)malloc(sizeof(*p));
    p->top = -1;
    return p;
}
//压栈
int Push(Stack *p,int x) {
    if (p->top == MAX_LEN - 1) {
        return -1;
    }
    p->top++;
    p->data[p->top] = x;
    return 0;
}
//出栈
int Pop(Stack *L,int *x) {
    if (L->top == -1) {
        return -1;
    }
    //利用传出参数传出栈顶元素
    *x = L->data[L->top];
    L->top--;
    return 0;
}
//栈顶
int TOP(Stack *L,int *x) {
    if (L->top == -1) {
        return -1;
    }
    *x = L->data[L->top];
    return 0;
}
//判断栈是否为空
int Empty(Stack *L) {
    return (L->top == -1);
}
//定义符号的优先级
int Priority(int ope) {
    switch(ope) {
    case '(':   return 0;  //左括号已经在栈内时，如果比较，其优先级最低
    case '+':
    case '-':   return 1;
    case '*':
    case '%':
    case '/':   return 2;
    case '^':  return 3;
    default :   return -1;
    }
}
// 将两个数出栈、根据ope符号计算，然后再次入栈
void Calculation(Stack *snum,int ope) {
    int n,n1,n2;
    Pop(snum,&n1);
    Pop(snum,&n2);
    switch(ope) {
        case '+':   n = n1 + n2; break;
        case '-':   n = n2 - n1; break;
        case '*':   n = n1 * n2; break;
        case '/':   n = n2 / n1; break;
        case '%':   n = n2 % n1; break;
        case '^':   n = pow(n2,n1);break;
    }
    Push(snum,n);
}
// 先处理除右括号外的符号
void Deal_ope(Stack *snum,Stack *sope,int ope) {
    int old_ope;
    if (Empty(sope) || ope == '(') {
        Push(sope,ope);
        return ;
    }
    TOP(sope,&old_ope);
    if (Priority(ope) > Priority(old_ope)) {
        //传入符号大于当前栈顶，则将传入符号入栈
        Push(sope,ope);
        return ;
    }
    //如果传入的符号优先级小于当前栈顶符号
    while (Priority(ope) <= Priority(old_ope)) {
        //将当前栈顶的符号取出与数字栈中顶端的两个数字进行计算
        Pop(sope,&old_ope);
        printf("%c ",old_ope);
        Calculation(snum,old_ope);
        if (Empty(sope)) {
            break;
        }
        //再次取出一个当前栈符号与传入符号比较，循环
        TOP(sope,&old_ope);
    }
    Push(sope,ope);
}
//单独处理右括号
void Right(Stack *snum,Stack *sope) {
    int old_ope;
    TOP(sope,&old_ope);
    while (old_ope != '(')  {
        //当前符号出栈然后将数字出栈两个进行计算,在括号内优先级最高
        Pop(sope,&old_ope);
        printf("%c ",old_ope);
        Calculation(snum,old_ope);
        //循环
        TOP(sope,&old_ope);
    }
    Pop(sope,&old_ope);//出现左括号时将它丢弃
}
// 打印数字栈
void Display(Stack *L) {
    int i;
    if (L->top == -1) {
        return;
    }
    for (i = 0 ; i <= L->top; i++) {
        printf("%d ",L->data[i]);
    }
    printf("\n");
}
//打印符号栈
void Displayope(Stack *L) {
    int i;
    if (L->top == -1) {
        return ;
    }
    for (i = 0 ; i <= L->top; i++) {
        printf("%c ",L->data[i]);
    }
    printf("\n");
}

int main() {
    char str[] = "10+(2*10+9)/5";
    char dst[MAX];
    printf("中缀表达式为:");
    printf("%s\n",str);
    int i = 0,value = 0,flag = 0;   //数字的值
    int old_ope;
    Stack *numstack,*opestack;
    numstack = Createstack();  // 创建存放数字的栈
    opestack = Createstack();  // 创建存放运算符的栈
    printf("后缀表达式为:");
    //printf("栈的变化如下：\n");
    /* 表达式字符串解析函数,然后将高优先级的符号/(*)进行计算重新入栈
       退出while大家的优先级都一样*/
    while (str[i] != '\0') {
        if (str[i] >= '0' && str[i] <= '9') {
            value *= 10;        //数字的获取，注意可能不止一位
            value +=str[i]-'0';
            flag = 1;
        } else {
            if (flag) {   //flag = 1说明value里面存储了数字，将其入栈
                printf("%d ",value);
                Push (numstack, value);
                //flag标志清零，value存放数字的变量清零
                flag = 0;
                value = 0;
                //Display(numstack);
            }
            if(str[i] == ')') {
                Right(numstack,opestack);
                //Displayope(opestack);
            } else {
                Deal_ope(numstack,opestack,str[i]);
                //Displayope(opestack);
            }
        }
        i++;
    }
    if (flag) { //如果flag = 1.说明value里面还有数值,将其入栈
        printf("%d ",value);
        Push(numstack,value);
        //Display(numstack);
    }
    while (!Empty(opestack)) {//如果符号栈不为空，继续计算
        Pop(opestack,&old_ope);
        printf("%c ",old_ope);
        Calculation(numstack,old_ope);
        //Displayope(opestack);
    }
    Pop(numstack,&value); //最终答案
    printf("\n%s = %d\n",str,value);
    return 0;
}