算术表达式求值

中缀表达式

      我们平时写的表达式称为中缀表达式。

      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;
}