BUAA_数据结构_5TH_3. 计算器（表达式计算-表达式树实现）_计算器(表达式计算-表达式树实现

BUAA_数据结构_5TH_3. 计算器（表达式计算-表达式树实现）

第五次作业链接

1. 树叶节点遍历（树-基础题）
2. 词频统计（树实现）
4. 网络打印机选择

题目描述：

从标准输入中读入一个整数算术运算表达式，如24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ，计算表达式结果，并输出。
要求：
1、表达式运算符只有+、-、*、/，表达式末尾的=字符表示表达式输入结束，表达式中可能会出现空格；
2、表达式中会出现圆括号，括号可能嵌套，不会出现错误的表达式；
3、出现除号/时，以整数相除进行运算，结果仍为整数，例如：5/3结果应为1。
4、要求采用表达式树来实现表达式计算。

输入形式

从键盘输入一个以=结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。

输出形式

首先在屏幕上输出表达式树根、左子节点及右子节点上的运算符或操作数，中间由一个空格分隔，最后有一个回车（如果无某节点，则该项不输出）。然后输出表达式计算结果。

样例输入

24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 ) =

样例输出

* / /
18

易错点

1.后缀表达式的求解

参考代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define maxn 1000
typedef struct op_or_num{
    int flag;//1:num 2:op
    int num;
    char op;
}node;
node reverse[maxn+10];
int reverse_pos;
char middle[maxn+10];

int is_number(char x);
char reverse_op_stack[maxn+10];
int pos_reverse_op;
void reverse_push(char temp);
char reverse_pop();
int reverse_is_empty();
char look();
int get_pri(char x);

typedef struct tree{
    node x;
    struct tree *lc,*rc;
}tree,*tree_ptr;
tree *expression[maxn+10];
int expression_pos;

tree_ptr create_node(node x,tree_ptr lc,tree_ptr rc);
void push_expression(tree_ptr temp);
tree_ptr pop_expression();
int is_expression_empty();
void print(tree_ptr temp);

int num_stack[maxn+10];
void push_num(int num);
int pop_num();
int is_num_empty();
int cal(char op,int num1,int num2);
int num_pos;

int main()
{
    pos_reverse_op=-1;
    expression_pos=-1;
    num_pos=-1;
    gets(middle);
    int len=strlen(middle);
    for(int i=0;i<len;i++){
        if(is_number(middle[i])){
            int num=0;
            while(is_number(middle[i])){
                num=num*10+middle[i]-'0';
                i++;
            }
            node temp;
            temp.num=num;
            temp.flag=1;
            reverse[reverse_pos++]=temp;
        }
        if(middle[i]==' ') continue;
        if(middle[i]=='=') break;
        if(middle[i]==')'){
            while(1){
                char op=reverse_pop();
                if(op=='('){
                    break;
                }
                node temp;
                temp.flag=2;
                temp.op=op;
                reverse[reverse_pos++]=temp;
            }
        }
        else{
            if(reverse_is_empty()){
                reverse_push(middle[i]);
                continue;
            }
            else{
                char stack_top=look();
                while(get_pri(stack_top)>=get_pri(middle[i])){
                    if(stack_top=='(') break;
                    char op=reverse_pop();
                    node temp;
                    temp.flag=2;
                    temp.op=op;
                    reverse[reverse_pos++]=temp;
                    if(reverse_is_empty()) break;
                    stack_top=look();
                }
                reverse_push(middle[i]);
            }
        }
    }
    while(!reverse_is_empty()){
        char op=reverse_pop();
        node temp;
        temp.flag=2;
        temp.op=op;
        reverse[reverse_pos++]=temp;
    }//获得后缀表达式
    /*
    for(int i=0;i<reverse_pos;i++){
        if(reverse[i].flag==1){
            printf("%d ",reverse[i].num);
        }else{
            printf("%c ",reverse[i].op);
        }
    }
    printf("\n");
    */
    tree_ptr root;//建表达式树
    for(int i=0;i<reverse_pos;i++){
        if(reverse[i].flag==1){
            tree_ptr temp=create_node(reverse[i],NULL,NULL);
            push_expression(temp);
        }else{
            tree_ptr T1=pop_expression();
            tree_ptr T2=pop_expression();
            tree_ptr temp=create_node(reverse[i],T2,T1);
            push_expression(temp);
        }
    }
    root=pop_expression();
    print(root);
    if(root->lc){
        printf(" ");
        print(root->lc);
    }
    if(root->rc){
        printf(" ");
        print(root->rc);
    }
    printf("\n");
    for(int i=0;i<reverse_pos;i++){//求结果
        if(reverse[i].flag==1){
            push_num(reverse[i].num);
        }else{
            int num2=pop_num();
            int num1=pop_num();
            int res_temp=cal(reverse[i].op,num1,num2);
            push_num(res_temp);
        }
    }
    int res=pop_num();
    printf("%d\n",res);
    return 0;
}

int is_number(char x)
{
    if(x>='0'&&x<='9') return 1;
    else return 0;
}

void reverse_push(char temp)
{
    reverse_op_stack[++pos_reverse_op]=temp;
}

char reverse_pop()
{
    char temp=reverse_op_stack[pos_reverse_op];
    pos_reverse_op--;
    return temp;
}

int reverse_is_empty()
{
    if(pos_reverse_op==-1) return 1;
    else return 0;
}

char look()
{
    return reverse_op_stack[pos_reverse_op];
}

int get_pri(char x)
{
    switch(x){
        case '+':
            return 0;
        case '-':
            return 0;
        case '*':
            return 1;
        case '/':
            return 1;
        case '%':
            return 1;
        case '(':
            return 2;
        case ')':
            return 2;
    }
}

tree_ptr create_node(node x,tree_ptr lc,tree_ptr rc)
{
    tree_ptr temp=(tree_ptr)malloc(sizeof(tree));
    temp->lc=lc;
    temp->rc=rc;
    temp->x=x;
    return temp;
}

void push_expression(tree_ptr temp)
{
    expression[++expression_pos]=temp;
}

tree_ptr pop_expression()
{
    tree_ptr temp=expression[expression_pos];
    expression_pos--;
    return temp;
}

int is_expression_empty()
{
    return expression_pos==-1?1:0;
}

void print(tree_ptr temp)
{
    if(temp->x.flag==1){
        printf("%d",temp->x.num);
    }else{
        printf("%c",temp->x.op);
    }
}

void push_num(int num)
{
    num_stack[++num_pos]=num;
}

int pop_num()
{
    int temp=num_stack[num_pos];
    num_pos--;
    return temp;
}

int is_num_empty()
{
    return num_pos==-1?1:0;
}

int cal(char op,int num1,int num2)
{
    switch(op){
        case '+':
            return num1+num2;
        case '-':
            return num1-num2;
        case '*':
            return num1*num2;
        case '/':
            return num1/num2;
        case '%':
            return num1%num2;
    }
}


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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270

有问题或bug 欢迎私戳/评论