首先允许我吐槽CSDN的MARKDOWN，简直难用的不行。
程序的原理是将表达式分治转换为二叉树，再在二叉树上递归计算结果。如同以下表达式：x+5*y-(6/(1-5.5))可以表达为以下二叉树（抱歉，，本来想弄Visualgo的，结果上不了，只能用word来做画面了）：
为什么是这样的二叉树呢？仔细想想平时是怎么计算这个表达式的，毫无疑问的是最后一步是减法，倒数的第二步是加法和除法……所以我们不难得出，将最后一步作为整个树的根，然后将这次运算的左边的表达式（可能是运算、未知数、常数）和右边的表达式进行递归建树，就能建立这样的二叉树了。
那为什么要建立这个二叉树呢？如果这样的二叉树建立好了，就很容易递归（从下至上）得到答案了：
那么现在的问题就在于如何将表达式字符串转换为表达式树，从先前的说明中，我们不难发现，关键就在于寻找当前表达式中的最后一步，作为子树的根。为了达到这个目的，我们首先去除掉包含整个表达式的括号，这样一来，最后一步计算一定不在括号中，这里可以用一个变量brackets来标记，初始化brackets=0，每当遇到左括号就++，右括号就–，所以，当且仅当brackets==0时，当前的位置是处在括号外的。在扫的过程中，不断的更新在括号外的最后加减法和最后乘除法的位置。最后得到的加减法的位置（如果没有加减法，就用乘除）就是当前表达式的最后运算。
未知数的处理是靠map实现的。
整个程序由基类表达式类和三个继承自表达式类的类组成，其中Evaluate函数（返回计算数据）由Expression类定义，由三个派生类重写。函数strToTree是将字符串转换为表达式二叉树：
详细见代码，注释写的非常详细：
#include<iostream>#include<vector>#include<cstdio>#include<map>#include<cstring>#include<string>using namespace std;typedef map<string, double> MSD;//表达式类class Expression{public:virtual double Evaluate(MSD vars){ return 0; }};//常数类class Constant :public Expression{public:double value;Constant(double value){this->value = value;}double Evaluate(MSD vars){return value;}};//未知数类class VariableReference :public Expression{public:string name;VariableReference(string name){this->name = name;}double Evaluate(MSD vars){double value = vars[name];return value;}};//运算类class Operation :public Expression{public://左边的表达式Expression *left;//当前运算char op;//右边的表达式Expression *right;Operation(Expression *left, char op, Expression *right){this->left = left;this->op = op;this->right = right;}//计算值double Evaluate(MSD vars){//递归计算double x = left->Evaluate(vars);double y = right->Evaluate(vars);//运算switch (op){case '+':return x + y;case '-':return x – y;case '*':return x*y;case '/':return x / y;}}};//将字符串转换为树//s起始位置，t结束位置Expression *strToTree(string str, int s, int t){//去除包含整个当前表达式的括号while (s <= t&&str[s] == '('&&str[t] == ')')s++, t–;if (s > t)return new Constant(0);//findLetter找到字母，用以判断是否为未知数//findChar找到字符，用以判断是否存在运算符bool findLetter = false, findChar = false;//括号标记int brackets = 0;//lastPS最后的加减法//lastMD最后的乘除int lastPS = -1, lastMD = -1;for (int i = s; i <= t; i++){//当前位置不是常数if (str[i] != '.' && (str[i]<'0' || str[i]>'9')){//如果是字母的话if ((str[i] >= 'a'&&str[i] <= 'z') || (str[i] >= 'A'&&str[i] <= 'Z'))findLetter = true;else{//不是常数，不是字母，就是运算符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;}}}}//从s到t都是常数if (findLetter == false && findChar == false)return new Constant(stod(str.substr(s, t – s + 1)));//从s到t是未知数if (findChar == false)return new VariableReference(str.substr(s, t – s + 1));//从s到t是个运算//没有加减就用乘除if (lastPS == -1)lastPS = lastMD;return new Operation(strToTree(str, s, lastPS – 1), str[lastPS], strToTree(str, lastPS + 1, t));}int main(){MSD vars;//这里设置未知数vars["x"] = 123;vars["y"] = 100;//输入字符串string str;cin >> str;//转换为树Expression *exp = strToTree(str, 0, str.length() – 1);//输出值cout << exp->Evaluate(vars) << endl;return 0;}这里我设置了两个未知数x，y。运行结果如下图所示：你在雨中行走，你从不打伞，你有自己的天空，它从不下雨。
