算术表达式求值
中缀表达式
我们平时写的表达式称为中缀表达式。
eg: 1. 2 - 3*4 +5 2. 2* (3- 5) +7
正如上面的表达式,我们在计算的过程中,首先要注意运算符的优先级,其次要注意括号。 我们应如何判断运算符的优先级以及如何进行运算。
后缀表达式
首先,我们可以将中缀表达式转化为后缀表达式(逆波兰表达式),然后进行运算。如何将中缀表达式转化为后缀表达式呢?规则如下:
将上面的中缀表达式转化为后缀表达式:1. 2 3 4 * - 5 + 2. 2 3 - 5 * 7 +
后缀表达式如何进行计算
借助栈,依次遍历后缀表达式,当遇到操作数时,直接进行入栈。当遇到操作符时,弹出栈中的两个元素,依次作为右操作数和左操作数,将计算后的结果压入栈中。最后栈中剩余的元素,则为表达式的值。
代码实现:
#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
//判断是操作符还是操作数
enum Cal_Type
{
OP_NUM,
OP_SYMBOL,
};
struct Cell
{
Cal_Type _type;//计算类型
int _value;
Cell(const Cal_Type& t, const int& x)
:_type(t)
,_value(x)
{}
};
class Calculator
{
public:
Calculator(const vector<int> &exp)
:_infix(exp)
{}
int Count()
{
Transition(); //将中缀表达式转化为后缀表达式
stack<int> num; //中间计算过程中的操作数
int n = _exp.size();
for(int i=0; i<n; ++i)
{
Cell cur = _exp[i];
if(cur._type == OP_NUM)
{
num.push(cur._value);
}
else if(cur._type == OP_SYMBOL)
{
int d2 = num.top(); //右操作数
num.pop();
int d1 = num.top(); //左操作数
num.pop();
int sum = 0;
switch(cur._value)
{
case '+':
{sum = d1+d2;}
break;
case '-':
{sum = d1-d2;}
break;
case '*':
{sum = d1*d2;}
break;
case '/':
{sum = d1/d2;}
break;
default:
break;
}
num.push(sum);
}
}
return num.top();
}
//判断是否为操作符
bool IsTypied(char op)
{
switch(op)
{
case '-':
case '+':
case '*':
case '/':
return true;
default:
return false;
break;
}
}
//确定操作符的优先级
int Priority(char op)
{
switch(op)
{
case '-':
case '+':
return 1;
case '*':
case '/':
return 2;
default:
break;
}
return -1;
}
//中缀转后缀表达式
void Transition()
{
stack<int> tmp; //用于保存遇到‘(’时的运算符
for(int i=0; i<_infix.size(); ++i)
{
if((_infix[i]+48)>='0' && (_infix[i]+48)<='9')//当遇到数字时,直接插入后缀表达式中
{
Cell c(OP_NUM,_infix[i]);
_exp.push_back(c);
}
else if(_infix[i] == '(')
{
tmp.push(_infix[i]);
}
else if(_infix[i] == ')')
{
while(tmp.top() != '(')
{
_exp.push_back(Cell(OP_SYMBOL,tmp.top()));
tmp.pop();
}
tmp.pop();
}
else if(IsTypied(_infix[i])) //如果为运算符,应该判断优先级
{
if(tmp.empty() || Priority(_infix[i]) > Priority(tmp.top()))//如果tmp为NULL的话,只需要判断栈顶元素和_infix[i]的优先级
{
tmp.push(_infix[i]);
}
else
{
while(!tmp.empty() && Priority(_infix[i]) <= Priority(tmp.top()))
{
_exp.push_back(Cell(OP_SYMBOL,tmp.top()));
tmp.pop();
}
tmp.push(_infix[i]);
}
}
else
{
cout<<"输入有误"<<endl;
_exp.clear();
return ;
}
}
//如果tmp 不为NULL的话,全部压入_exp中
while(!tmp.empty())
{
_exp.push_back(Cell(OP_SYMBOL,tmp.top()));
tmp.pop();
}
}
private:
vector<int> _infix; //中缀表达式
vector<Cell> _exp; //后缀表达式
};
void Test()
{
int a[] = {2,'-',3,'*',4,'+',5};
vector<int> exp(a,a+sizeof(a)/sizeof(a[0]));
Calculator c(exp);
cout<<c.Count()<<endl;
}