半小时速成算术表达式求值 （数据结构课程设计）

半小时速成算术表达式求值 （数据结构课程设计）
中缀表达式
什么是中缀表达式？中缀表达式就是我们平时写的计算式的式子！

格式:"操作数1  操作符  操作数2"
 12 * (3 + 4) - 6 + 8 / 2;  // 中缀表达式

  

 

  
1
  
2
 

中缀表达式如果要先计算操作符优先级低的两个数，比如上面要优先计算3+4，这里就必须带括号，指明计算的优先级，负责就会按照操作符默认的优先级来计算。

后缀表达式（逆波兰表达式）
什么是后缀表达式？

格式："操作数  操作符"
12 3 4 + * 6 - 8 2 / +; //后缀表达式

  

 

  
1
  
2
 

后缀表达式如何计算表达式
这里栈就派上用场了，从左到右一个个遍历表达式，遇到操作数就入栈，遇到操作符就依次取出栈顶的两个操作数进行计算，并把计算结果入栈，供后面计算，直到栈为空，说明表达式计算完毕，否则说明表达式有问题。过程如下图：

思想：

从中缀表达式中从左往右依次取出数据
如遇到操作数，直接输出到后缀的队列里。
如果遇到操作符（包括括号），这里再定义一个存放操作符的栈，则:
i.如果操作符是'(',入栈
ii.如果操作符是')',则把栈里的操作符依次出栈并插入到后缀序列后面，直到遇到')'.
iii.如果操作符不是‘(’和‘)’,则：
     (1). 如果操作符的优先级比top的优先级高，则入栈
     (2).如果操作符优先级等于或小于top优先级，则将top出栈并插入到后缀序列后面，pop后,再比较栈顶元素的优先级，重复iii，直到把此操作符      插入，将此操作符入栈。
如果中序队列里的数据已经读取完毕，记录操作符的栈里，还有操作符的话，依次出栈插入到后缀序列的后面。
此时中缀就已经转换为后缀表达式,如下图

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

代码讲解部分：

主函数
int main(){
    numStack *num = (numStack *)malloc(sizeof(numStack));
    fuStack *fu= (fuStack *)malloc(sizeof(fuStack));
    char msg[MAX_SIZE];
    initStack(num);//将栈进行初始化
    initFuStack(fu);
    scanf("%s",msg);//输入字符串
    getPreExpression(num,fu,msg);//将后缀表达式输出，同时将它的运算结果输出
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

栈1

typedef struct Num{
    int msg[MAX_SIZE];
    int top;
}numStack;
void initStack(numStack *num){
    num->top = 0;
}//初始化栈堆

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

栈2

typedef struct FU{
    char msg[MAX_SIZE];
    int top;
}fuStack;
void initFuStack(fuStack *fu){
    fu->top = 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

将后缀表达式输出，同时将它的运算结果输出

void getPreExpression(numStack *num,fuStack *fu,char *msg){
   int i,result,j,k = 0,a,b,count = 0;//count表示数字的个数
   char ch,tmp,arr[MAX_SIZE];//arr数组用于多位数字的拼接,ch表示当前的字符，tmp表示fuStack的栈顶元素
   for(i = 0; msg[i] != '\0'; i++){
       ch = msg[i];
       if(isNum(ch)){
           j = i;
           k = 0;//重置k
           //拼接数字
           while(isNum(msg[j])){
               arr[k++] = msg[j];
               j++;
           }
           arr[k] = '\0';//这一步十分重要

           i = j - 1;
           a = atoi(arr);//调用atoi方法，从而将这个多位数字的字符串转成整形数字
           count++;
           if(count == 1)
               printf("%d",a);//如果是第一个数字，那么前面不需要输出一个空格，否则要在前面输出空格
           else
               printf(" %d",a);
           push(num,a);//将数字压入栈中
       }else{
           //如果是运算符，那么需要分情况讨论
           if(isFuEmpty(fu) || ch == '('){
               //如果栈为空或者当前字符为左括号，直接将当前符号压入栈中
               pushFu(fu,ch);
           }else{
               getFuTop(fu,&tmp);
               if(tmp == '('){
                   //如果栈顶元素是一个左括号，那么直接入栈
                   pushFu(fu,ch);
               }else{
                 //当前的字符不是一个左括号，那么需要判断当前的符号是否为一个右括号
                 if(ch == ')'){
                   getFuTop(fu,&tmp);
                   while(tmp != '('){
                      popFu(fu,&tmp);
                      printf(" %c",tmp);
                      if(!yunsuan(tmp,num,&result)){
                         printf("被除数不可以为0，运算错误!!!\n");
                         return;
                      }
                      push(num,result);//如果运算符合运算法则，那么将运算结果压入到栈中
                      getFuTop(fu,&tmp);
                   }
                   popFu(fu,&tmp);
                 }else{
                    //当前的符号是一个普通符号，那么需要比较优先级
                    label:
                        if(isFuEmpty(fu) || level(ch) > level(tmp)){
                               //当前符号的优先级大于栈顶符号的优先级，那么直接入栈
                           pushFu(fu,ch);
                        }else{
                            //当前的符号的优先级小于等于栈顶符号的优先级，那么将栈顶元素从fu栈中跳出并输出
                           popFu(fu,&tmp);
                           printf(" %c",tmp);
                           if(!yunsuan(tmp,num,&result)){
                               printf("被除数不可以为0，运算错误!!!\n");
                               return;
                           }
                           push(num,result);//如果运算符合运算法则，那么将运算结果压入到栈中
                           getFuTop(fu,&tmp);
                           goto label;//利用goto语句，从而实现当前的符号的优先级小于栈顶符号的优先级，然后将其压入
                        }
                 }
               }
           }

       }
   }
   //将num压入到fu栈中
   while(!isFuEmpty(fu)){
        popFu(fu,&tmp);
        printf(" %c",tmp);
        if(!yunsuan(tmp,num,&result)){
        //将进行相应的运算，然后将对应的运算结果赋值给result
           printf("被除数不可以为0，运算错误!!!\n");
           return;
        }
        push(num,result);//如果运算符合运算法则，那么将运算结果压入到栈中
   }
   printf("\n");
   pop(num,&a);//将num中的栈顶元素的值赋给a，并将其删除
   printf("%s的运算结果为%d\n",msg,a);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
 

判断是否为数字子函数

int isNum(char ch){
   if(ch >= '0' && ch <= '9')
       return 1;
   return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
 

判断栈为空

int isFuEmpty(fuStack *fu){
    return fu->top == 0;
}

  

 

  
1
  
2
  
3
 

压栈子函数

int pushFu(fuStack *fu,char e){
    if(fu->top == MAX_SIZE)
        return ERROR;
    fu->msg[fu->top++] = e;
    return OK;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

判断左括号子函数

int getFuTop(fuStack *fu,char *e){
    if(fu->top == 0)
        return ERROR;
    *e = fu->msg[fu->top - 1];
    return OK;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

循环压数子函数

int popFu(fuStack *fu,char *e){
    if(fu->top == 0)
        return ERROR;
    *e = fu->msg[--fu->top];
    return OK;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

压栈子函数

int push(numStack *num,int e){
    if(num->top == MAX_SIZE)
        return ERROR;
    num->msg[num->top++] = e;
    return OK;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

全部代码展示

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 21
#define ERROR 0
#define OK 1
typedef struct Num{
    int msg[MAX_SIZE];
    int top;
}numStack;
void initStack(numStack *num){
    num->top = 0;
}//初始化栈堆

int push(numStack *num,int e){
    if(num->top == MAX_SIZE)
        return ERROR;
    num->msg[num->top++] = e;
    return OK;
}
int pop(numStack *num,int *e){
    if(num->top == 0)
        return ERROR;
    *e = num->msg[--num->top];
    return OK;
}
int getTop(numStack *num,int *e){
    if(num->top == 0)
        return ERROR;
    *e = num->msg[num->top - 1];
    return OK;
}
int isEmpty(numStack *num){
    return num->top == 0;
}
typedef struct FU{
    char msg[MAX_SIZE];
    int top;
}fuStack;
void initFuStack(fuStack *fu){
    fu->top = 0;
}

int pushFu(fuStack *fu,char e){
    if(fu->top == MAX_SIZE)
        return ERROR;
    fu->msg[fu->top++] = e;
    return OK;
}
int popFu(fuStack *fu,char *e){
    if(fu->top == 0)
        return ERROR;
    *e = fu->msg[--fu->top];
    return OK;
}
int getFuTop(fuStack *fu,char *e){
    if(fu->top == 0)
        return ERROR;
    *e = fu->msg[fu->top - 1];
    return OK;
}
int isFuEmpty(fuStack *fu){
    return fu->top == 0;
}
int level(char ch){
    if(ch == '+' || ch == '-')
        return 1;
    else if(ch == '*' || ch == '/')
        return 2;
    else
        return 0;
}
int isNum(char ch){
    if(ch >= '0' && ch <= '9')
        return 1;
    return 0;
}
int yunsuan(char ch,numStack *num,int *result){
   int a,b;
   pop(num,&a);
   pop(num,&b);//将从栈中跳出两个元素，并将他们的值赋给a、b

   switch(ch){
      case '+':
          *result = b + a;
           break;
      case '-':
          *result = b - a;
           break;
      case '*':
          *result = b * a;
           break;
      case '/':
          if(a == 0){
            return ERROR;//如果不符合运算法则，那么返回ERROR
          }
          *result = b / a;
          break;
   }
   return OK;
}
void getPreExpression(numStack *num,fuStack *fu,char *msg){
    int i,result,j,k = 0,a,b,count = 0;//count表示数字的个数
    char ch,tmp,arr[MAX_SIZE];//arr数组用于多位数字的拼接,ch表示当前的字符，tmp表示fuStack的栈顶元素
    for(i = 0; msg[i] != '\0'; i++){
        ch = msg[i];
        if(isNum(ch)){
            j = i;
            k = 0;//重置k
            //拼接数字
            while(isNum(msg[j])){
                arr[k++] = msg[j];
                j++;
            }
            arr[k] = '\0';//这一步十分重要

            i = j - 1;
            a = atoi(arr);//调用atoi方法，从而将这个多位数字的字符串转成整形数字
            count++;
            if(count == 1)
                printf("%d",a);//如果是第一个数字，那么前面不需要输出一个空格，否则要在前面输出空格
            else
                printf(" %d",a);
            push(num,a);//将数字压入栈中
        }else{
            //如果是运算符，那么需要分情况讨论
            if(isFuEmpty(fu) || ch == '('){
                //如果栈为空或者当前字符为左括号，直接将当前符号压入栈中
                pushFu(fu,ch);
            }else{
                getFuTop(fu,&tmp);
                if(tmp == '('){
                    //如果栈顶元素是一个左括号，那么直接入栈
                    pushFu(fu,ch);
                }else{
                  //当前的字符不是一个左括号，那么需要判断当前的符号是否为一个右括号
                  if(ch == ')'){
                    getFuTop(fu,&tmp);
                    while(tmp != '('){
                       popFu(fu,&tmp);
                       printf(" %c",tmp);
                       if(!yunsuan(tmp,num,&result)){
                          printf("被除数不可以为0，运算错误!!!\n");
                          return;
                       }
                       push(num,result);//如果运算符合运算法则，那么将运算结果压入到栈中
                       getFuTop(fu,&tmp);
                    }
                    popFu(fu,&tmp);
                  }else{
                     //当前的符号是一个普通符号，那么需要比较优先级
                     label:
                         if(isFuEmpty(fu) || level(ch) > level(tmp)){
                                //当前符号的优先级大于栈顶符号的优先级，那么直接入栈
                            pushFu(fu,ch);
                         }else{
                             //当前的符号的优先级小于等于栈顶符号的优先级，那么将栈顶元素从fu栈中跳出并输出
                            popFu(fu,&tmp);
                            printf(" %c",tmp);
                            if(!yunsuan(tmp,num,&result)){
                                printf("被除数不可以为0，运算错误!!!\n");
                                return;
                            }
                            push(num,result);//如果运算符合运算法则，那么将运算结果压入到栈中
                            getFuTop(fu,&tmp);
                            goto label;//利用goto语句，从而实现当前的符号的优先级小于栈顶符号的优先级，然后将其压入
                         }
                  }
                }
            }

        }
    }
    //将num压入到fu栈中
    while(!isFuEmpty(fu)){
         popFu(fu,&tmp);
         printf(" %c",tmp);
         if(!yunsuan(tmp,num,&result)){
         //将进行相应的运算，然后将对应的运算结果赋值给result
            printf("被除数不可以为0，运算错误!!!\n");
            return;
         }
         push(num,result);//如果运算符合运算法则，那么将运算结果压入到栈中
    }
    printf("\n");
    pop(num,&a);//将num中的栈顶元素的值赋给a，并将其删除
    printf("%s的运算结果为%d\n",msg,a);
}
int main(){
    numStack *num = (numStack *)malloc(sizeof(numStack));
    fuStack *fu= (fuStack *)malloc(sizeof(fuStack));
    char msg[MAX_SIZE];
    initStack(num);//将栈进行初始化
    initFuStack(fu);
    scanf("%s",msg);//输入字符串
    getPreExpression(num,fu,msg);//将后缀表达式输出，同时将它的运算结果输出
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
  
187
  
188
  
189
  
190
  
191
  
192
  
193
  
194
  
195
  
196
  
197
  
198
  
199
  
200
 

文章来源: blog.csdn.net，作者：上进小菜猪，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_52908342/article/details/118274093