-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.cpp
More file actions
247 lines (243 loc) · 6.86 KB
/
Copy pathmain.cpp
File metadata and controls
247 lines (243 loc) · 6.86 KB
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
#include <cstring>
#include <iomanip>
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef struct
{ //运算符栈
char *base;
char *top;
int stacksize;
} SqStack1;
int InitStack1(SqStack1 &S)
{ //运算符栈初始化
S.base = new char[MAXSIZE];
if (!S.base)
return OVERFLOW;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
int Push1(SqStack1 &S, char e)
{ //运算符栈入栈
if (S.top - S.base == S.stacksize) //栈满
return ERROR;
*S.top = e;
S.top++;
return OK;
}
int Pop1(SqStack1 &S)
{ //运算符栈出栈
if (S.top == S.base) //栈空
return ERROR;
S.top--;
return OK;
}
char GetTop1(SqStack1 S)
{ //运算符栈取栈顶元素
if (S.top != S.base)
return *(S.top - 1);
return ERROR;
}
typedef struct
{ //操作数栈
double *base;
double *top;
int stacksize;
} SqStack2;
int InitStack2(SqStack2 &S)
{ //操作数栈初始化
S.base = new double[MAXSIZE];
if (!S.base)
return OVERFLOW;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
int Push2(SqStack2 &S, double e)
{ //操作数栈入栈
if (S.top - S.base == S.stacksize) //栈满
return ERROR;
*S.top = e;
S.top++;
return OK;
}
int Pop2(SqStack2 &S)
{ //操作数栈出栈
if (S.top == S.base) //栈空
return ERROR;
S.top--;
return OK;
}
double GetTop2(SqStack2 S)
{ //操作数栈取栈顶元素
if (S.top != S.base)
return *(S.top - 1);
return ERROR;
}
double Calculate(double a, char op, double b)
{ //计算表达式“a op b”的值
switch (op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
}
char Precede(char a, char b)
{ //比较运算符a和b的优先级
if ((a == '(' && b == ')') || (a == '=' && b == '='))
return '=';
else if (a == '(' || a == '=' || b == '(' ||
((a == '+' || a == '-') && (b == '*' || b == '/')))
return '<';
else
return '>';
}
double EvaluateExpression(SqStack1 OPTR, SqStack2 OPND, char s[])
{ //算术表达式求值的算符优先算法
/**************begin************/
int i = 0, p1 = 0;
// i是循环用的变量 p1是字符串当前位置下标
double a, b;
//操作数
char op;
//操作符
char *temp = new char[strlen(s)];
//临时字符串用于存放操作数
while (1)
{
if (s[p1] == '=')
{
while (OPTR.top - 1 != OPTR.base)
{
op = GetTop1(OPTR);
Pop1(OPTR);
//弹操作符栈
a = GetTop2(OPND);
Pop2(OPND);
//弹操作数栈
b = GetTop2(OPND);
Pop2(OPND);
//弹操作数栈
Push2(OPND, (op != '-' && op != '/') ? Calculate(a, op, b)
: Calculate(b, op, a));
}
goto CalcEnd;
}
if (s[p1] == '+' || s[p1] == '-' || s[p1] == '*' || s[p1] == '/' ||
s[p1] == '(' || s[p1] == ')')
//是否为操作符
{
switch (Precede(GetTop1(OPTR), s[p1]))
{
case '=': {
Pop1(OPTR);
//弹操作符栈
break;
}
case '>': {
op = GetTop1(OPTR);
Pop1(OPTR);
//弹操作符栈
a = GetTop2(OPND);
Pop2(OPND);
//弹操作数栈
b = GetTop2(OPND);
Pop2(OPND);
//弹操作数栈
Push2(OPND, (op != '-' && op != '/') ? Calculate(a, op, b)
: Calculate(b, op, a));
//入操作数栈
if (s[p1] == ')')
{
while (GetTop1(OPTR) != '(')
{
op = GetTop1(OPTR);
Pop1(OPTR);
//弹操作符栈
a = GetTop2(OPND);
Pop2(OPND);
//弹操作数栈
b = GetTop2(OPND);
Pop2(OPND);
//弹操作数栈
Push2(OPND, (op != '-' && op != '/')
? Calculate(a, op, b)
: Calculate(b, op, a));
}
Pop1(OPTR);
//弹出栈顶(
}
else
{
Push1(OPTR, s[p1]);
}
//回括的话弹出所有
break;
}
case '<': {
Push1(OPTR, s[p1]);
//入操作符栈
break;
}
}
p1++;
}
else
{
if (s[p1] != '+' && s[p1] != '-' && s[p1] != '*' && s[p1] != '/' &&
s[p1] != '(' && s[p1] != ')' && s[p1] != '=')
{
while (s[p1] != '+' && s[p1] != '-' && s[p1] != '*' &&
s[p1] != '/' && s[p1] != '(' && s[p1] != ')' &&
s[p1] != '=')
{
temp[i] = s[p1];
i++;
p1++;
}
//操作数提取到temp字符串
temp[i] = '\0';
//字符串结尾null
Push2(OPND, stod(temp));
//字符串转double
i = 0;
// temp字符串下标归零
}
}
}
CalcEnd:
delete[] temp;
//用完delete
a = GetTop2(OPND);
Pop2(OPND);
return a;
/**************end************/
}
int main()
{ //设OPTR和OPND分别为运算符栈和操作数栈
SqStack1 OPTR;
InitStack1(OPTR); //初始化OPND栈
SqStack2 OPND;
InitStack2(OPND); //初始化OPTR栈
Push1(OPTR, '='); //将表达式起始符“=”压入OPTR栈
char s[100];
while (cin >> s)
{ //循环读入多组数据
if (s[0] == '=')
break; //当表达式只有一个“=”时，输入结束
//输出中缀算术表达式的值
cout << fixed << setprecision(2) << EvaluateExpression(OPTR, OPND, s)
<< fixed << setprecision(2) << endl;
}
return 0;
}