#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<sstream>
#include<cctype>
#include<stdio.h>
using namespace std;
class Calculator //计算类
{
private:
string expression; //中缀表达式
vector<string>postexpression; //后缀表达式
bool BracketMatch() const; //检查括号是否匹配
bool CheckCharException() const; //检查表达式字符是不是有非法字符
bool CheckFormat() const; //检查表达式格式是否合法
inline bool IsOperator(char c) const
{
if(c=='+' || c=='-' || c=='*' || c=='/') return true;
return false;
}
bool Priority(char op1,char op2) const; //若操作符op1优先级大于op2,则返回真,否则返回假,op2已经在堆栈中
void ToPostexpression(); //中缀表达式转向后缀表达式
double StringToDouble(const string s); //将字符串s转化为double数字
string DoubleToString(const double d); //将double数字转化为字符串
public:
Calculator(const string& str):expression(str)
{
cout<<expression<<endl;
cout<<"表达式初始化完毕!"<<endl;
}
void ValidityCheck() const; //对中缀表达式进行合法性检查
void ShowPost();
void Calculate(double& d); //计算表达式的值
};
bool Calculator::BracketMatch() const
{
int cnt=0; //cnt用于检查括号是否匹配,如果遇到左括号,cnt加1,遇到右括号,cnt减1
string::const_iterator it;
for(it=expression.begin();it!=expression.end();it++)
{
if(cnt<0) return false;
if(*it=='(') cnt++;
else if(*it==')') cnt--;
}
if(cnt!=0) return false;
else return true;
}
void Calculator::ValidityCheck() const
{
if(this->BracketMatch()==false)
{
cout<<"表达式不合法,程序退出!"<<endl;
exit(0);
}
if(this->CheckCharException()==false)
{
cout<<"表达式含有非法字符!"<<endl;
cout<<"表达式所含字符只能是数字0到9字符,'(',')','.'"<<endl;
exit(0);
}
if(this->CheckFormat()==false)
{
cout<<"表达式格式非法!"<<endl;
exit(0);
}
cout<<"表达式合法,程序进行中..."<<endl;
}
bool Calculator::CheckCharException() const
{
string::const_iterator it;
for(it=expression.begin();it!=expression.end();it++)
{
if(isdigit(*it) || *it=='(' || *it==')' || *it=='.' || this->IsOperator(*it)) continue;
else return false;
}
return true;
}
bool Calculator::CheckFormat() const
{
string::const_iterator it;
for(it=expression.begin();it!=expression.end();it++)
{
if(this->IsOperator(*it))
{
if(it+1==expression.end()) return false; //操作符不能是第一个或者最后一个字符
if(it==expression.begin()) return false;
char pre=*(it-1); //操作符前一个字符
char next=*(it+1); //操作符后一个字符
if(this->IsOperator(pre) || this->IsOperator(next)) return false; //操作符前后紧挨着字符不能是操作符
}
if(*it=='.')
{
if(it+1==expression.end()) return false; //'.'不能是第一个或者最后一个字符
if(it==expression.begin()) return false;
char pre=*(it-1); //'.'前一个字符
char next=*(it+1); //'.'后一个字符
if(!isdigit(pre) || !isdigit(next)) return false; //紧挨着'.'字符必须是数字字符
}
if(*it=='(')
{
if(it+1==expression.end()) return false; //'('不能是最后一个字符
char next=*(it+1);
if(next==')') return false; //'('之后不能是')'
}
if(*it==')')
{
if(it==expression.begin()) return false; //')'不能是第一个字符
char pre=*(it-1);
if(pre=='(') return false; //')'之前不能是'('
}
}
return true;
}
bool Calculator::Priority(char op1,char op2) const
{
if(op1=='+' || op1=='-')
{
switch(op2)
{
case '(': //此时'('在堆栈中,所以op1优先级大于op2
return true;
default:
return false;
}
}
if(op1=='*' || op1=='/')
{
switch(op2)
{
case '+':
return true;
case '-':
return true;
case '*':
return false;
case '/':
return false;
case '(':
return true;
}
}
if(op1=='(') //此时'('不在堆栈中
{
return true;
}
}
void Calculator::ToPostexpression() //核心代码
{
string temp; //临时字符串
string::const_iterator it;
stack<char>ss; //堆栈,用于存放操作符
bool flag=false; //表示处理操作数
for(it=expression.begin();it!=expression.end();it++)
{
if(isdigit(*it) || *it=='.')
{
temp+=*it;
flag=true;
}
else//此时遇到'(',或者')'或者'+','-','*','/'符号
{
if(flag) //现在开始处理操作数
{
this->postexpression.push_back(temp); //将操作数放入中缀表达式
temp=""; //temp清空
flag=false;
}
if(ss.empty()==true) ss.push(*it); //如果堆栈空,直接放入操作符
else
{
if(*it=='(') ss.push(*it); //遇到'('直接放入堆栈
else if(*it==')')
{
while(ss.top()!='(') //弹出堆栈中元素直到遇到'('
{
temp+=ss.top();
ss.pop();
this->postexpression.push_back(temp);
temp="";
}
ss.pop(); //弹出'('
}
else //此时处理是'+','-','*','/'
{
char op2=ss.top();
if(this->Priority(*it,op2)) ss.push(*it); //当前运算符优先级大于堆栈顶运算符优先级
else //弹出堆栈顶运算符,直到当前运算符优先级大于堆栈顶运算符优先级
{
do
{
temp+=ss.top();
this->postexpression.push_back(temp);
temp="";
ss.pop();
op2=ss.top();
}while(this->Priority(*it,op2)==false);
ss.push(*it); //此时堆栈已经没有优先级大于当前运算符的优先级,所以将当前运算符入栈
}
}
}
}
}
if(temp!="")
{
this->postexpression.push_back(temp); //譬如1+2的情况
temp="";
}
while(ss.empty()==false) //若果堆栈不空,弹出所有元素加入中缀表达式
{
temp+=ss.top();
this->postexpression.push_back(temp);
temp="";
ss.pop();
}
}
void Calculator::ShowPost()
{
vector<string>::const_iterator it;
this->ToPostexpression();
for(it=this->postexpression.begin();it!=this->postexpression.end();it++)
{
cout<<*it;
}
cout<<endl;
}
double Calculator::StringToDouble(const string s)
{
stringstream ss(s); //定义字符串流
double d;
ss>>d; //从流中提取
return d;
}
string Calculator::DoubleToString(const double d)
{
stringstream ss;
ss<<d; //将d加入字符串流
string s;
ss>>s; //从流中提取
return s;
}
void Calculator::Calculate(double &d) //核心代码
{
stack<string>s; //存放操作数
vector<string>::const_iterator it;
for(it=this->postexpression.begin();it!=this->postexpression.end();it++)
{
if(*it!="+" && *it!="-" && *it!="*" && *it!="/") //遇到是操作数
{
s.push(*it);
}
else
{
string operand2=s.top(); //取出堆栈两个操作数的字符串,转化为浮点型运算后,将结果转化为字符串放入堆栈
s.pop();
string operand1=s.top();
s.pop();
double op1,op2;
op1=this->StringToDouble(operand1);
op2=this->StringToDouble(operand2);
double result;
if(*it=="+")
{
result=op1+op2;
}
if(*it=="-")
{
result=op1-op2;
}
if(*it=="*")
{
result=op1*op2;
}
if(*it=="/")
{
result=op1/op2;
}
string strresult=this->DoubleToString(result);
s.push(strresult);
}
}
d=this->StringToDouble(s.top());
}
void main()
{
string str;
cout<<"请输入一个字符串表达式:";
getline(cin,str);
Calculator cal(str);
cal.ValidityCheck();
cout<<"表达式的后缀表达式是:";
cal.ShowPost();
double d;
cal.Calculate(d);
cout<<"结果是:"<<d<<endl;
}