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
| // 字符栈
typedef struct {
char data[MAXSIZE];
int top;
} Stack;
void InitStack(Stack **s) {
*s = (Stack*)malloc(sizeof(Stack));
(*s)->top = -1;
}
bool Push(Stack *s, char e) {
if (s->top == MAXSIZE - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(Stack **s, char *e) {
if ((*s)->top == -1)
return false;
*e = (*s)->data[(*s)->top];
(*s)->top--;
return true;
}
bool GetTop(Stack **s, char *e) {
if ((*s)->top == -1)
return false;
*e = (*s)->data[(*s)->top];
return true;
}
bool StackEmpty(Stack **s) {
if ((*s)->top == -1)
return true;
return false;
}
// 将中缀表达式转换成后缀表达式
void trans(char *exp, char postexp[]) {
int i = 0;
char e;
Stack *Optr;
InitStack(&Optr); //初始化操作符栈，为存储后缀表达式做准备
while (*exp != '\0') { // 对每个字符进行判断处理
switch (*exp) {
//单独处理括号
//如果是左括号，直接入栈
case '(':
Push(Optr, '(');
exp++;
break;
//如果为右括号，一直出栈操作，直到将 ( 也出栈
case ')':
Pop(&Optr, &e);
while (e != '(') {
postexp[i++] = e;
Pop(&Optr, &e);
}
exp++;
break;
// + - 优先级相同，当做同一种情况处理
case '+':
case '-':
//由于 + - 的优先级只比 ( 大，所有只要栈顶字符不为 ( 就一直出栈；反之，则将 + - 入栈。
while (!StackEmpty(&Optr)) {
GetTop(&Optr, &e);
if (e == '(')
break;
else {
postexp[i++] = e;
Pop(&Optr, &e);
}
}
//最后将 + - 入栈
Push(Optr, *exp);
exp++;
break;
case '*':
case '/':
// * / 优先级比 * / ^ ! 小，所有如果栈顶运算符是它们，就出栈；反之就将 * / 入栈
while (!StackEmpty(&Optr)) {
GetTop(&Optr, &e);
if (e == '/' || e == '*' || e == '^' || e == '!') // * / 的优先级仅仅低于它前面的 * /，
高于前面的 + -，所以要将前面的 * / 弹出栈；+ - 保留，因为新的 * / 会放在栈低，优先级高。 {
postexp[i++] = e;
Pop(&Optr, &e);
} else
break; // 其他情况（ + - 左括号 ）退出，
}
//最后将 / * 入栈
Push(Optr, *exp);
exp++;
break;
case '^':
// ^ 优先级仅比 ^ ! 小，如果栈顶运算符是它们，则出栈；反之将 ^ 入栈
while (!StackEmpty(&Optr)) {
GetTop(&Optr, &e);
if (e == '^' || e == '!') {
postexp[i++] = e;
Pop(&Optr, &e);
} else
break; // 其他情况（ + - * / ( ）退出，
}
Push(Optr, *exp); //最后将 ^ 入栈
exp++;
break;
case '!':
// ! 优先级仅比 ! 小，所有如果栈顶运算符为 !,则将其出栈；反之，将 ! 入栈
while (!StackEmpty(&Optr)) {
GetTop(&Optr, &e);
if (e == '!') {
postexp[i++] = e;
Pop(&Optr, &e);
} else
break; // 其他情况（ + - * / ^ ( ）退出，
}
//最后将 ! 入栈
Push(Optr, *exp);
exp++;
break;
default:
while (*exp > '0' && *exp < '9') //循环判断是否为数字字符，如果是则保存到postexp，循环判断是
因为可能是多位数字 {
postexp[i++] = *exp;
exp++;
}
//以#分隔各个数字字符
postexp[i++] = '#';
}
}
while (!StackEmpty(&Optr)) { //扫描完exp后，操作符栈可能还有操作符，将其存到postexp
Pop(&Optr, &e);
postexp[i++] = e;
}
postexp[i] = '\0'; //结束字符串
free(Optr); //销毁栈
}
|
