核心算法:
mid=FormatMid(mid); //格式化中缀表达式
JudgeLegalMid(mid); //判断中缀表达式的合法性
MidToPost mtp(mid);
mtp.ToPost(post); //中缀表达式转后缀表达式
cout <<"结果:" <<Calc(post) <<endl; //计算后缀表达式
具体过程——
第一步:格式化中缀表达式
这一步的目的是为了解决“-”的歧义问题:有时候“-”是一元运算符,有时候“-”是二元运算符。可以用一种巧妙的方案解决歧义——在一元运算符的“-”前面添上0。这样,此后就可以把+-*/统一当做二元运算符处理。
具体代码:(放在FormatMid.h文件中)
#include<string>
#include<vector>
#include<iostream>
using namespace std;
string FormatMid(string mid)
{
for (int i=0;i<mid.length();i++)
{
if (mid[i]=='-' && (i==0||mid[i-1]=='('))
{
mid.insert(i,"0");
i++;
}
}
string realmid="";
for (int i=0;i<mid.length();i++)
{
if (mid[i]!='-')
{
realmid+=mid[i];
}
else
{
int cou=0;
while (mid[i]=='-') i++,cou++;
if (cou%2==0) realmid+='+';
else realmid+='-';
i--;
}
}
return realmid;
}
第二步:判断中缀表达式的合法性
这一步也是为了程序的鲁棒性,具体代码如下:(放在JudgeLegalMid.h文件中)
#include<iostream>
#include<cstring>
#include<vector>
#include<string>
using namespace std;
void illegal()
{
cout <<"表达式不合法!" <<endl;
exit(1);
}
bool isysf(char cc)
{
if (cc=='+' || cc=='-' || cc=='*' || cc=='/') return true;
else return false;
}
void JudgeLegalMid(string &c)
{
int l=c.length();
if (!isdigit(c[0]) && c[0]!='(') illegal(); //首位不是(也不是数字,不合法
if (!isdigit(c[l-1]) && c[l-1]!=')') illegal(); //末位不是)也不是数字,不合法
int now=0; //括号不匹配,不合法
for (int i=0;i<l;i++)
{
if (c[i]=='(') now++;
else if (c[i]==')') now--;
if (now<0) illegal();
}
if (now!=0) illegal();
for (int i=1;i<l-1;i++)
{
if (c[i]=='+' || c[i]=='*' || c[i]=='/' || c[i]=='-') //二元运算符
{
if (!isdigit(c[i-1]) && c[i-1]!=')') //左边不是)也不是数字,不合法
illegal();
if (!isdigit(c[i+1]) && c[i+1]!='(') //右边不是(也不是数字,不合法
illegal();
}
if (c[i]=='.' && !isdigit(c[i-1]) && !isdigit(c[i+1])) illegal(); //.左右不是数字,不合法
}
for (int i=1;i<l;i++) //.向左右扩展 ,在遇到运算符之前,只能扩展出数字才合法
{
if (c[i]=='.')
{
int j=i-1,k=i+1;
while (j>0 && isdigit(c[j])) j--;
while (k<l && isdigit(c[k])) k++;
if (c[j]=='.' || c[k]=='.') illegal();
}
}
}
第三步:中缀表达式转后缀表达式
这一步是比较经典的栈处理,具体代码如下:(放在MidToPost.h文件中,封装成了类)
#ifndef MIDTOPOST_H____
#define MIDTOPOST_H____
#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<string>
#include<sstream>
using namespace std;
string cts(char cc)
{
stringstream stream;
stream << cc;
return stream.str();
}
class MidToPost
{
private:
string c;
stack<string> s;
int yxj(char ope); //返回一个运算符的优先级
public:
MidToPost(const string cc); //构造函数
void ToPost(vector<string>& res); //转为后缀表达式
string readnum(int p);
};
int MidToPost::yxj(char ope)
{
if (ope=='*' || ope=='/') return 1;
if (ope=='+' || ope=='-') return 0;
if (ope=='@' || ope=='(') return -1;
}
string MidToPost::readnum(int p)
{
string s="";
while (isdigit(c[p]) || c[p]=='.')
{
s+=cts(c[p]);
p++;
}
return s;
}
MidToPost::MidToPost(const string cc)
{
c=cc;
while (!s.empty()) s.pop();
s.push(string("@"));
}
void MidToPost::ToPost(vector<string>& res)
{
res.clear();
int now=0;
int l=c.length();
for (int i=0;i<l;i++)
{
if (isdigit(c[i]))
{
res.push_back(readnum(i));
while (isdigit(c[i]) || c[i]=='.') i++;
i--;
}
else if (c[i]=='(') s.push(cts(c[i]));
else if (c[i]==')')
{
while (s.top()[0]!='(')
{
res.push_back(s.top());
s.pop();
}
s.pop();
}
else
{
int k1,k2;
k1=yxj(s.top()[0]);
k2=yxj(c[i]);
while (k1>=k2)
{
res.push_back(s.top());
s.pop();
k1=yxj(s.top()[0]);
k2=yxj(c[i]);
}
s.push(cts(c[i]));
}
}
while (s.top()[0]!='@')
{
res.push_back(s.top());
s.pop();
}
}
#endif
第四步:计算后缀表达式的值
同样是经典的栈处理,对于除数为0的情况由于C++自带inf所以就没有特判。代码如下:(放在CalcPost.h文件中)
#include<iostream>
#include<cstring>
#include<vector>
#include<string>
#include<vector>
#include<sstream>
using namespace std;
stack<double> s;
double Calc(vector<string> & c)
{
while (!s.empty()) s.pop();
int l=c.size();
for (int i=0;i<l;i++)
{
if (isdigit(c[i][0]))
{
stringstream ss(c[i]);
double tmp;
ss >>tmp;
s.push(tmp);
}
else
{
double res2=s.top();
s.pop();
double res1=s.top();
s.pop();
switch(c[i][0])
{
case '+':res1+=res2;break;
case '-':res1-=res2;break;
case '*':res1*=res2;break;
case '/':res1/=res2;break;
}
s.push(res1);
}
}
return s.top();
}
主程序:
#include"MidToPost.h"
#include"CalcPost.h"
#include"JudgeLegalMid.h"
#include"FormatMid.h"
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
const int maxn=2000;
string mid;
vector<string> post;
int main()
{
cout <<"请输入中缀表达式(实数加减乘除括号运算):";
while (cin >>mid)
{
mid=FormatMid(mid);
cout <<"等价转换后的中缀表达式:" <<mid <<endl;
JudgeLegalMid(mid);
MidToPost mtp(mid);
mtp.ToPost(post);
cout <<"后缀表达式:";
for (int i=0;i<post.size();i++)
cout <<post[i]<<" ";
cout <<endl;
cout <<"结果:" <<Calc(post) <<endl;
cout <<"请输入中缀表达式(实数加减乘除括号运算):";
}
return 0;
}
运行结果:
原文链接: https://www.cnblogs.com/itlqs/p/5994900.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/242762
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!