借助栈实现中缀表达式转后缀表达式并计算结果(限+-*/()运算符)

原理


整体过程:输入中缀字符串存入str1->中缀转后缀表达式存入字符串str2–>利用后缀表达式字符串str2计算结果并输出

1.中缀—>后缀

  • 按照顺序扫描str1遇到数字或者小数点直接存入str2,这里我们使用循环一次性将数符输入再在其后添加标记符号这里我使用美元符号作为分隔,防止后面使用的时候若两个数符同时储存判别不出数符。
  • 遇到运算符,判断优先级,再只有+-*/()的运算中我们根据中缀转后缀的方法提取出如下特点:
    • 左括号优先级最大,直接压入栈不必考虑其他,同时记录左括号个数
    • */优先级其次,对有无括号的分析后发现我们可以化简为一个操作
      • *和/法则遇到同级别 运算符才出栈存入str2再入栈该符号,遇到+-(直接压栈即可
    • +-运算符优先级最低,只要入栈就需要清栈存入str2再压栈,但是需要分为有括号和无括号两个操作
      • 有括号:清空左括号后的字符存入str2再压栈
      • 无括号:直接清空栈存入str2,再压栈
    • 遇到右括号则出栈最近的一个左括号所有右面的符号,同时左括号个数-1
  • 直到str1扫描完毕,str2的后缀表达式也就生成了

2.后缀表达式计算

  • 按照顺序扫描str2,遇到数字字符或者小数点直接进入循环判断将一整个数字字符串存入一个临时数组,由于我们之前使用的分隔符,所以可以依靠分隔符很容易就扫描出每个数字字符串,之后我们直接调用c库中的atof()函数转为浮点型再压栈
  • 遇到运算符则出栈两个数字通过该运算符计算后再压栈,直到扫描结束,栈顶数据就是计算结果

代码实现


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
//计科1803 刘峻源 
#include<iostream>
#include<string.h>
# include <stdlib.h>
using namespace std;
int defaultSize=500;
int t=0; //用于数组下标,不用每次传入函数
int flag=0;//用于判断栈内是否有'('
template<class T>
class stack
{
public:
stack();
T pop();
void push(T a);
T getTop();
void cleanTokuohao(T str2[]);//用于括号清栈
void clean(T str2[]); //用于+-清栈
void clean2(T str2[]); //用于*/清栈
protected:
T *data;
int top=-1;
};
template<class T>
stack<T>::stack()
{
data=new T[defaultSize];
top=-1;
}
template<class T>
T stack<T>::pop()
{
if(top>-1)
return data[top--];
}
template<class T>
void stack<T>::push(T a)
{
if(top<defaultSize-1)
data[++top]=a;
}
template<class T>
T stack<T>::getTop()
{
if(top>-1)
return data[top];
}
template<class T>
void stack<T>::cleanTokuohao(T str2[])//用于括号清栈
{
while(data[top]!='(')
{
str2[t++]=pop();
}
top--;
}
template<class T>
void stack<T>::clean(T str2[])//用于+-清栈
{
while(top!=-1)
{
str2[t++]=pop();
}
}
template<class T>
void stack<T>::clean2(T str2[])//用于*/清栈
{
while(data[top]=='/'||data[top]=='*')
{
str2[t++]=pop();
}
}
char* ZhuanHuan(char str1[])
{
stack<char> s1;
//s1使用栈操作符号
char *str2;
//str2储存后缀表达式
int len=strlen(str1)-1;
//储存长度,节省循环调用strlen的时间
str2=new char[defaultSize];
for(int i=0;i<len;i++)
{ //cout<<str2<<endl;
if((str1[i]>='0'&&str1[i]<='9')||str1[i]=='.')
{
while((str1[i]>='0'&&str1[i]<='9')||str1[i]=='.')
{
//扫描到数字时一次性将数字全部扫进去
str2[t++]=str1[i++];
}
str2[t++]='$';
//将美元符作为分割实数的符号方便分析
i--;
//最后别忘了i需要退格
}
//数字或者'.'直接入后缀表达式str2
else if(str1[i]=='(')
{
//左括号直接入符号栈因为左括号优先级最高不需要考虑
s1.push(str1[i]);
//同时记录左括号个数方便其他出栈判断操作
flag++;
}
else if(str1[i]==')')
{
//遇到右括号开始出栈到左括号
s1.cleanTokuohao(str2);
//括号标记减1;
flag--;
}
else if(str1[i]=='+'||str1[i]=='-')
{
if(flag==0)
{
s1.clean(str2);
//无括号的时候,在本题只有四则运算的情况,+-优先级最低,清栈后将再将+或者-填进去
s1.push(str1[i]);
}
else
{
s1.cleanTokuohao(str2);
//有括号相当于出栈该括号内的符号再将+填入左括号之后,这里直接调用括号清除函数,再手动添加'('和'+'或者'-';
s1.push('(');
s1.push(str1[i]);
}
}
else if(str1[i]=='*'||str1[i]=='/')
{
//*和/法则遇到同级别 运算符才出栈再入栈,遇到+-(直接入栈即可,
s1.clean2(str2);
s1.push(str1[i]);
}
}
s1.clean(str2);
return str2;
}
double houzhijisuan(char str[])
{
stack<double> s1;
//利用栈储存数字
char num[500];
//作为中转字符转数字
int len=strlen(str);
double num1,num2;
//作为中转计算数据
for(int i=0;i<strlen(str);i++)
{
if((str[i]>='0'&&str[i]<='9')||str[i]=='.')
{
t=0;
//静态变量t再次利用。
while(str[i]!='$')
{
//扫描到数字时一次性将数字全部扫进去
num[t++]=str[i++];
}
num[t]='\0';
//别忘记加\0否则会误判数字
s1.push(atof(num));
//将数字入栈,这里利用了C库中的atof()函数帮我们省去了自己编写的工夫
}
//之后都是遇到运算符就出栈两个数据根据运算符计算结果再入栈,不再赘述.
else if(str[i]=='+')
{
num1=s1.pop();
num2=s1.pop();
s1.push(num2+num1);
}
else if(str[i]=='-')
{
num1=s1.pop();
num2=s1.pop();
s1.push(num2-num1);
}
else if(str[i]=='*')
{
num1=s1.pop();
num2=s1.pop();
s1.push(num2*num1);
}
else if(str[i]=='/')
{
num1=s1.pop();
num2=s1.pop();
s1.push(num2/num1);
}
}
return s1.getTop();
}
int main()
{
char str[defaultSize];
cin>>str;
cout<<houzhijisuan(ZhuanHuan(str));
}
-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~