一、算法思路
先看下只有 + 和 * 的。
输入长度为\(n\)的字符串，例如：$ 1 + 2 + 3 * 4 * 5$
输出表达式的值，即：\(63\)
“表达式求值”问题，两个核心关键点：
（1）双栈，一个操作数栈，一个运算符栈；
（2）运算符优先级:"栈顶运算符"与"即将入栈的运算符"的优先级比较：
-
如果栈顶的运算符优先级低，新运算符直接入栈。
-
如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈。
举个栗子
\(1+2+3 * 4 *5\)，看是如何利用上述两个关键点实施计算的。
首先，这个例子只有+和*两个运算符，所以它的运算符表是：
（1）如果栈顶是+，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；
（2）如果栈顶是+，即将入栈的是*，栈顶优先级低，直接入栈；
（3）如果栈顶是*，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；
（4）如果栈顶是*，即将入栈的是*，栈顶优先级高，需要先计算，再入栈；
有了运算符表，一切就好办了。
一开始，初始化好输入的字符串，以及操作数栈，运算符栈。
一步步，扫描字符串，操作数一个个入栈，运算符也入栈。
下一个操作符要入栈时，需要先比较优先级。
栈内的优先级高，必须先计算，才能入栈。
计算的过程为：
（1）操作数出栈，作为\(num2\)；
（2）操作数出栈，作为\(num1\)；
（3）运算符出栈，作为\(op\)；
（4）计算出结果；
（5）结果入操作数栈；
接下来，运算符和操作数才能继续入栈。下一个操作符要入栈时，继续比较与栈顶的优先级。
栈内的优先级低，可以直接入栈。
字符串继续移动。
又要比较优先级了。
栈内的优先级高，还是先计算（3*4=12），再入栈。
不断入栈，直到字符串扫描完毕。
不断出栈，直到得到最终结果\(3+60=63\)，算法完成。
这个方法的时间复杂度为\(O(n)\)，整个字符串只需要扫描一遍。
运算符有\(+\)、 \(-\)、\(*\)、 \(/\)、 \((\)、 \()\)、 \(\{\) 、 \(\}\) 都没问题，如果共有\(n\)个运算符，会有一个\(n*n\)的优先级表。
二、完整思路
本题的综合性还是很强的，有以下知识点：
-
运算符优先级表
-
左括号直接入操作符栈，右括号不入操作符栈，看到右括号，就不断的处理操作符栈，直到看到左括号，再把左括号弹出。
-
抽象出从一个字符串中读取数字的办法。
-
抽象出两个数字通过数字栈、操作符栈进行计算的通用办法。
三、完整代码
#include <bits/stdc++.h>
using namespace std;
stack<int> num;//数字栈
stack<char> op;//操作符栈
//优先级表
unordered_map<char, int> h{{'+', 1},
{'-', 1},
{'*', 2},
{'/', 2}};
/**
* 功能：计算两个数的和差积商
*/
void eval() {
int a = num.top();//第二个操作数
num.pop();
int b = num.top();//第一个操作数
num.pop();
char p = op.top();//运算符
op.pop();
int r = 0;//结果
//计算结果
if (p == '+') r = b + a;
else if (p == '-') r = b - a;
else if (p == '*') r = b * a;
else if (p == '/') r = b / a;
//结果入栈
num.push(r);
}
/**
* 功能：从指定字符串s中，位置i开始读取一个数字出来
* @param s 指定的字符串s
* @param i 指定的开始位置i，最终修改后返回，返回时它的位置是此数字的结束位置
* @param x 读取到的数字
*/
void readNum(string s, int &i, int &x) {
//从字符串中读取数字的标准模板代码
while (i < s.size() && isdigit(s[i])) {
x = x * 10 + s[i] - '0';
i++;//最后会找到不是数字，或者出了s.size()
}
//在循环里加冒了，需要返回一步,方便下一个人开始
i--;
}
int main() {
//读入表达式
string s;
cin >> s;
//遍历字符串的每一位
for (int i = 0; i < s.size(); i++) {
//数字则入栈
if (isdigit(s[i])) {
//读出完整的数字
int x = 0;
readNum(s, i, x);
num.push(x);//数字入栈
}
//左括号直接入栈
else if (s[i] == '(') op.push(s[i]);
//右括号需要做小结，把它与前面一个左括号之内的计算做完
else if (s[i] == ')') {
while (op.top() != '(') eval(); //将左右括号之间的计算完，维护回栈里
//左括号出栈
op.pop();
} else {//运算符
//如果待入栈运算符优先级低，则先计算
//h[s[i]]:新读入的操作符优先级
//h[op.top()]:栈顶的操作符优先级
//>=表示不管是大于，还是等于，都让原来的先算完，再算新来的运算符，
// 可以理解为+，-比* / 优先级低，同样的是+-,那么从左到右，左先右后。
while (op.size() && h[op.top()] >= h[s[i]]) eval();
op.push(s[i]);//操作符入栈
}
}
while (op.size()) eval();//剩余的完成计算
cout << num.top() << endl;//输出
return 0;
}