1）有无括号
2）一种优先级运算符（只有+-或*/) 还是2种（+- 和*/都有）
3) 求逆波兰序列，求值，求表达式树
两种思路
1.分治 （求值，和求表达式树都可以用）nlogn
1）先去掉冗余括号（两边最外面的，如(1), (1 + 2) )，如果有的话。找到优先级最小的运算符的位置p，如果不存在，说明是一个数字，返回atoi后的值
2）两边递归求值
3）对两边的值应用该运算符，返回结果。
对于找最小运算符：在括号内的不考虑，因为其优先级更高，同一优先级的运算符，前面的优先级高，后面的低。
map<char, function<int(int, int)>> = {{'+', [](int a, int b) {return a + b;}}, {'-', [](int a, int b) {return a - b;}}};
int eval(string &s, int l, int r) {
for (; l < r && s[l] == '( && s[r] == ')'; ++l, --r ) ;
int p = findLowestOp(s, l, r);
if (p == -1) return stoi(s.substr(l, r - l + 1));
return op[s[p]](eval(s, l, p - 1), eval(s, p + 1, r));
}
int findLowestOp(string &s, int l, int r) {
int p = -1 , nestedLevel = 0;
for (int i = l; i <= r; ++i) {
if (s[i] == '(') ++nestedLevel;
else if (s[i] == ')') --nestedLevel;
else if (string("+-*/").find(s[i]) != string ::npos && nestedLevel == 0 && (p < 0 || s[i] == '+' || s[i] == '-' || s[p] == '*' || s[p] == '/' )) p = i;
}
return p;
}
2 利用单调栈 O(n)
算法主要参与者：
1）操作符函数映射表
2）操作数栈operand，操作符栈op
3）token stream (可以先用操作符split，也可以实时tokenize)
算法框架：token 流加一个结束符#，依次取token：
1）如果token是操作数，atoi, 入operand栈
2）token是操作符，while token优先级比op栈顶元素低，则取op栈顶操作符做运算，相应的操作数是operand栈的最近的两个数
对于括号，可以看作是一种分界，左括号可以看作是一个新的op栈的栈底， 右括号可以看作是括号内表达式的结束符。
def evaluateExpression(self, expression):
m = {'+' : lambda a, b : a + b, '-' : lambda a, b : a - b, '*' : lambda a, b : a * b, '/' : lambda a, b : a / b}
op, oprand = [], []
for token in expression + ['#']:
if token.isdigit(): oprand.append(int(token))
else:
while len(op) > 0 and token != '(' and op[-1] != '(' and (token in '#)+-' or op[-1] in '*/'):
b = oprand.pop();
oprand[-1] = m[op.pop()](oprand[-1], b)
if token == ')': op.pop()
else: op.append(token)
if len(oprand) > 0: return oprand[-1]
return 0
详细解释条件判断部分：
len(op) > 0 和 op[-1]!= '(' 都是判断当前栈不为空（左括号mark一个新op栈的开始）
token != '(' 表示这不是一个“复合操作数”，括号代表一个子表达式，是值，这里比较的是运算符。
token in '#)+=' 当前运算符是这些，肯定不如栈顶运算符优先级高
op[-1] in '*/' 栈顶上已经是最高优先级的
一个逆向问题，给定一组数A，添加操作符使得表达式值为给定target
t是表达式最后一个term，
def solve(A, i, v, t, target, e):
if i == len(A):
if v == target: print e
else:
if i == 0: solve(A, i + 1, A[i], A[i], target, str(A[i]))
else:
solve(A, i + 1, v + A[i], A[i], target, e + '+' + str(A[i]))
solve(A, i + 1, v - A[i], -A[i], target, e + '-' + str(A[i]))
solve(A, i + 1, v - t + t * A[i], f * A[i], target, e + '*' + str(A[i]))
if A[i] != 0: solve(A, i + 1, v - t + t / A[i], f / A[i], target, e + '/' + str(A[i]))
