C++表达式求值（利用二叉树和栈分别描述）_利用二叉树求解表达式的值

求例如“（123-5）*6+（9-8）*（5-6）-（10-2*（3-9））”这样的表达式的值。

此类问题有两种方法可以解答，第一种是利用二叉树的性质，构建表达树栈。第二种方法是利用两个栈，一个放运算符，一个放数据，通过优先级顺序进行运算操作。

1）利用二叉树描述

     首先建立表达式树栈，把整个表达式按照优先级分解成各个子表达式，把子表达式分配给二叉树的节点构成表达树栈。表达树栈建好之后就可以从根节点开始递归计算表达式的值。表达树栈的建立过程如下：

struct expression
{//表达式
	char op;
	expression* left;
	expression* right;
	double value;
	expression(char theOp):op(theOp),left(nullptr),right(nullptr){  }
	expression(double theValue) :value(theValue), op('#') {
		left = right = nullptr;
	}
};
class expTree
{//表达式树
public:
	expTree(const string& str)
	{//构造树
		int n = str.size() - 1;
		GenExpTree(str, 0,n, root);
	}
	~expTree() { postOrderErase(root); } //析构树
	void postOrderErase(expression* &exp)
	{//后序删除
		if (exp != nullptr) {
			postOrderErase(exp->left);
			postOrderErase(exp->right);
			delete exp;
		}
	}
	double calculate() { return myCal(root); }
	double myCal(expression* &exp)
	{
		if (exp != nullptr) {
			if (exp->op == '#') {
				return exp->value;
			}
			double x = myCal(exp->left);
			double y = myCal(exp->right);
			switch (exp->op)
			{
			case'+':return x + y;
			case'-':return x -y;
			case'*':return x*y;
			case'/':return x / y;
			}
		}
	}
private:
	expression* root;
	void GenExpTree(const string& str, int b, int e, expression* & exp)
	{
		if (b<e&&str[b] == '(') {//找到和第一个括号相匹配的')'
			int i = 0,j=b;
			for (; j <= e;j++) {
				if (str[j]== '(') {
					++i;
				}
				else if (str[j]== ')') {
					--i;
				}
				if (i == 0) {
					break;
				}
			}
			if (j ==e) {//只有括号是对称的才消除,否则例如（）（）（）这种不能消除
				++b, --e;
			}
		}
		if (b > e) {
			exp = nullptr;
			return;
		}
		int brackets = 0;
		int lastPS = -1, lastMD = -1;
		bool findChar=false;
		for (int i = b; i <=e; i++)
		{
			if (str[i] != '.'&&str[i]<'0' || str[i]>'9') {//非常量
				findChar = true;
				switch(str[i])
				{
				  case'(': brackets++; break;
				  case')': brackets--; break;
         
				  case'+': 
				  case'-': if(!brackets)lastPS=i; break;
				  case'*':
				  case'/': if (!brackets)lastMD=i; break;
				}
			}
		}
		if (!findChar) {
			exp = new expression(stod(str.substr(b, e - b + 1)));
			return;
		}
		if (lastPS == -1) {
			lastPS = lastMD;
		}
		exp = new expression(str[lastPS]);
		GenExpTree(str, b, lastPS - 1, exp->left);
		GenExpTree(str, lastPS+1,e, exp->right);
	}
};
void testExpression()
{
    string str = "(123-5)*6+(9-8)*(5-6)-(10-2*(3+8))+8*(9-1)";
	expTree expT(str);
	cout << expT.calculate() << endl;   //输出783
}

2）利用两个栈来描述

    一个栈用来放运算符，另一个栈用来放数据。基本的思想是，如果运算符栈为空，则直接把运算符添加到运算符栈，否则，要比较栈外和栈内的运算符优先级，如果栈内的运算符优先级高（包括栈内的运算符和栈外的运算符处于一个优先级，也认为是栈内的优先级高）则把栈内运算符弹出，再把弹出两个数据符进行运算，把结果再次压入数据符栈,当然新来的运算符也要入运算符栈。如果栈外的运算符高，则直接把运算符压入运算符栈。如果遇见了‘)’，则说明有一对括号了，此时要把括号里的值计算好，把结果压入数据栈，当然‘)’不入栈，而且要把之前的‘(’删除。最后如果遍历过程中遇见的是数据符，则直接查找长度，把持续的数据先进行数据转换stod,再把结果压入数据栈。遍历完成后，也许因为优先级的关系，有些数据还没计算，此时的运算优先级是完全按照栈的出栈顺序来的，因此直接出栈计算，直到运算符栈为空，此时的数据栈也只剩一个元素就是最后的计算结果，返回此唯一的栈顶元素。

int priority(char a, char b)
{//a表示栈内的运算符，b表示栈外的运算符
	if (b == '+' || b == '-' )
	{
		if (a == '+' || a == '-' || a == '*' || a == '/') {//栈内的优先级高
			return 1;
		}
		else if (a == '(') {//栈外的优先级高
			return -1;
		}
	}
	else if (b == '*' || b == '/') {
		if (a == '*' || a == '/') {//栈内的优先级高
			return 1;
		}
		else if (a == '+' || a == '-' || a == '(') {//栈外的优先级高
			return -1;
		}
	}
	else if (b == '(') {//栈外的优先级高
		return -1;
	}
	return 0;
}
double calculate(double x, char op, double y)
{
	switch (op)
	{
	    case '+':return x + y;
		case '-':return x - y;
		case '*':return x * y;
		case '/':return x / y;
	}
}
double expStack(const string& str)
{
	stack<char> opor;
	stack<double>opnd;
	int i = 0;
	while (i < str.size()) {
		if (str[i] != '.'&&str[i]<'0' || str[i]>'9') {
			if (opor.empty() || priority(opor.top(), str[i]) < 0) {//栈外优先级高
				opor.push(str[i]);
			}
			else if (priority(opor.top(),str[i]) > 0) {//栈内优先级高
				double a = opnd.top();
				opnd.pop();
				double b = opnd.top();
				opnd.pop();
				opnd.push(calculate(b, opor.top(), a));
 
				opor.pop();
				opor.push(str[i]);
			}
			else if (str[i] == ')') {//计算括号里的值
				while (opor.top() != '(') {
					double a = opnd.top();
					opnd.pop();
					double b = opnd.top();
					opnd.pop();
					opnd.push(calculate(b, opor.top(), a));
 
					opor.pop();
				}
				opor.pop();
			}
			++i;
		}
		else {//常量
			int k = i;
			while (str[i] == '.' || str[i] >= '0'&&str[i] <='9') {
				i++;
			}
			opnd.push(stod(str.substr(k, i - k)));
		}
	}
	//计算剩余的数
	while (!opor.empty()) {
		double a = opnd.top();
		opnd.pop();
		double b = opnd.top();
		opnd.pop();
		opnd.push(calculate(b, opor.top(),a));
 
		opor.pop();
	}
	return opnd.top();
}
void testExpression()
{
	string str = "(123-5)*6+(9-8)*(5-6)-(10-2*(3+8))+8*(9-1)";
	//string str = "(9-7)*(5-6)";
	//string str = "4+3*(5+2/1)";
	cout << expStack(str) << endl;  //输出783
}