求含有数字、空格、加号、减号和小括号的数学计算式表达式字符串的计算结果。表达式只涉及到加减法，用1或-1乘数字累加得到结果，而且消掉括号。声明stack<int>，push1到栈中，遍历字符串，如果遇到加号，sign=s.top()，如果遇到减号，sign=-s.top()，如果遇到左括号，push sign到栈中，如果遇到右括号，pop栈首元素。
对于计算表达式字符串有个大一统的解法，代码如下：
// 考虑： + - * / 括号 空格 等元素，大统一解法
class Solution {
public:
struct Info{
int val; // 本地递归的执行结果
int idx; // 本次递归执行到哪个位置了
};
// 判断是否是数字字符
bool isdigit(char c) {
return c >= '0' && c <= '9';
}
// 入栈逻辑：根据sign判断分支
void addNum(stack<int>& stk, int num, char sign) {
int pre;
if (sign == '+') {
stk.push(num);
} else if (sign == '-') {
stk.push(-num);
} else if (sign == '/') {
pre = stk.top();
stk.pop();
stk.push(pre / num);
} else {
pre = stk.top();
stk.pop();
stk.push(pre * num);
}
return;
}
// 此次递归结束，计算当前栈中结果
int getNum (stack<int>& stk) {
int rval = 0;
while (!stk.empty()) {
rval += stk.top();
stk.pop();
}
return rval;
}
Info* f(string s, int i) {
Info* res = new Info();
int num = 0;
stack<int> stk;
char sign = '+';
while (i < s.size() && s[i] != ')') {
if (s[i] == ' ') { // 遇到空格，跳过
i ++;
continue;
}
if (isdigit(s[i])) { // 若当前位置是数字，则累加
num = num * 10 + (s[i++] - '0');
} else if (s[i] != '(') { // 遇到的是运算符，入栈
addNum(stk, num, sign);
sign = s[i ++];
num = 0;
} else if (s[i] == '(') { // 遇到了左括号，调递归
Info* t = f(s, i + 1);
num = t->val;
i = t->idx + 1;
}
}
// 到了结束位置或者遇到右括号，把上一个num入栈
addNum(stk, num, sign);
// 计算结果并返回
res->val = getNum(stk);
res->idx = i;
return res;
}
int calculate(string s) {
return f(s, 0)->val;
}
};
求逆波兰表达式的值。数字入栈，遇到运算符号，出栈两个数，计算结果，结果入栈，计算完栈首为结果。
数字串，求如何插入加号、减号和乘号使得最后的计算式结果等于target。回溯。定义计算式字符串expr，目前确认的计算式结果res和最右的连乘候选式的值，因为乘号优先级高于加减号，计算结果优先计算乘式再算加式，如何优雅地用程序计算好乘式和和式的实时结果，是这个编程题的一大难点，而我花费了两个小时解决该难点却无功而返，最终只能参考题解的处理方式。遍历数字串num，如果i==0，计算该段数字串的数值al，res=val，mul=val；若i>0，signIndex=expr.size(), expr.push_back(0), 如果新增的符号位是加号，res=res+val, mul=val；如果是减号，res=res-val, mul=-val；如果是乘号，res=res-mul+mul*val, mul=mul*val，递归回溯下去，直到遍历到数字串的末尾，如果res==target,ans.emplace_back(expr)。
四则运算式(无括号)字符串的取值。借鉴上题的思路，遍历时确认的结果res，最右候选乘式左边的值mul，上次遍历的运算符oc，取得这段数字m，根据oc的值如上题作相应的变换。遍历完成时的res即为结果
带括号的四则运算式字符串的取值。相比上题多了括号的处理，如大一统解法的理念括号里面的内容是子问题，由此深搜递归，dfs不仅需要返回子问题的字符串取值，还返回母问题新的遍历索引。
带括号、变量、部分变量初始化条件、乘号、加号、减号和数字的表达式字符串取值。核心的表达多项式的数据结构：map<string,int>，first表示项，second表示系数，实现多项式的加、减和乘，C++有isdigit函数判断字符是否为‘0‘-’9‘，变量名和运算符之间有空格分隔，巧妙地控制索引的增加，不需要讨论访问字符是否为空格的情况。其他内容还是考察四则运算计算的熟悉情况。
解析含数字、变量名、括号、空格和add、mult、let命令的lisp字符串的值，题解抄自拆分词法+变量表redo。根据括号的嵌套层数分解当前层的符号串。操作1定义如下：定义变量表，存储上一层的变量表，执行完当前层的操作后恢复为上一层的变量层。对要分析的带命令的符号串和带命令的子符号串递归执行操作1，母串的操作1结果即为问题解。
参考链接：224. 基本计算器
150. 逆波兰表达式求值
282. 给表达式添加运算符
227. 基本计算器 II
772. 基本计算器 III
770. 基本计算器 IV
736. Lisp 语法解析