表达式求值

github仓库：https://github.com/EanoJiang/Data-structures-and-algorithms

栈——表达式求值

枚举

1. typedef enum{
2.         枚举元素;
3. }枚举名;

复制代码

后缀表达式运算逻辑

遇到数字入栈，遇到符号出栈运算，运算结果入栈，\0结束

1. #include <stdio.h>
2. #include <stdlib.h>
4. typedef int ElemType;
5. #define MAXSIZE 100
7. typedef struct Stack{
8.     int top;
9.     ElemType *data;
10. }Stack;
13. // 初始化栈
14. Stack* initStack(){
15.     Stack *s = (Stack*)malloc(sizeof(Stack));
16.     s->data = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));
17.     s->top = -1;
18.     return s;
19. }
21. int isEmpty(Stack* s){
22.     return s->top == -1;
23. }
25. //入栈
26. int push(Stack *s, ElemType e){
27.     if(s->top == MAXSIZE-1){
28.         printf("栈满\n");
29.         return 0;
30.     }
31.     s->top++;
32.     //从栈顶入栈
33.     s->data[s->top] = e;
34.     return 1;
35. }
37. //出栈
38. ElemType pop(Stack *s,ElemType *e){
39.     if(s->top == -1){
40.         printf("栈空\n");
41.         return 0;
42.     }
43.     *e = s->data[s->top];
44.     s->top--;
45.     return *e;
46. }
48. //查看栈顶元素
49. ElemType getTop(Stack *s,ElemType *e){
50.     if(s->top == -1){
51.         printf("栈空\n");
52.         return 0;
53.     }
54.     *e = s->data[s->top];
55.     return *e;
56. }
58. typedef enum {
59.     LEFT_PARE,RIGHT_PARE,
60.     ADD,SUB,MUL,DIV,MOD,
61.     EOS,NUM
62. }contentType;
64. char expr[] = "82/2+56*-";
66. contentType getToken(char *symbol,int *index){
67.     //存储当前字符
68.     *symbol = expr[*index];
69.     //这句不能写成*index++：指针*index的地址自增
70.     *index = *index + 1;//指针*index的值自增
71.     switch(*symbol){
72.         case '(':
73.             return LEFT_PARE;
74.         case ')':
75.             return RIGHT_PARE;
76.         case '+':
77.             return ADD;
78.         case '-':
79.             return SUB;
80.         case '*':
81.             return MUL;
82.         case '/':
83.             return DIV;
84.         case '%':
85.             return MOD;
86.         case '\0':
87.             return EOS;
88.         default:
89.             if(*symbol >= '0' && *symbol <= '9'){
90.                 return NUM;
91.             }
92.             else{
93.                 printf("非法字符\n");
94.                 return -1;
95.             }
96.     }
97. }
99. //计算后缀表达式
100. int eval(Stack *s){
101.     char symbol;
102.     int op1,op2;
103.     int index = 0;
104.     ElemType result;
105.     contentType token;
106.     token = getToken(&symbol,&index);
107.     //结束条件\0
108.     while(token!= EOS){
109.         //遇到数字
110.         if(token == NUM){
111.             //将数字(字符相应ASCII码-'0')压入栈中
112.             push(s,symbol - '0');
113.         }
114.         //遇到操作符
115.         else{
116.             //出栈，把被操作数存到op2和op1中
117.             pop(s,&op2);
118.             pop(s,&op1);
119.             //计算结果入栈
120.             switch(token){
121.                 case ADD:
122.                     push(s,op1 + op2);
123.                     break;
124.                 case SUB:
125.                     push(s,op1 - op2);
126.                     break;
127.                 case MUL:
128.                     push(s,op1 * op2);  
129.                     break;
130.                 case DIV:
131.                     push(s,op1 / op2);
132.                     break;
133.                 case MOD:
134.                     push(s,op1 % op2);
135.                     break;
136.                 default:
137.                     printf("非法字符\n");
138.                     return 0;
139.             }
140.         }
141.         //更新token
142.         token = getToken(&symbol,&index);
143.     }
144.     //循环结束条件\0后，栈中只有一个元素，出栈并打印
145.     pop(s,&result);
146.     printf("结果为：%d\n",result);
147.     return 1;
148. }
151. int main(){
152.     Stack *s = initStack();
153.     eval(s);
154.     return 0;
156. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！