$\color{green}{<–画图不易，点下这里赞一下吧}$
网上看到的一篇，写的很详细。
思考思路：
先看下只有 + 和 * 的。
输入长度为n的字符串，例如：1+2+3*4*5
输出表达式的值，即：63
应该用什么数据结构？
栈。
应该先计算哪一步？
实际应该先计算1+2。
“表达式求值”问题，两个核心关键点：
（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，算法完成。
总结
“表达式求值”问题，两个核心关键点：
（1）双栈，一个操作数栈，一个运算符栈；
（2）运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：
如果栈顶的运算符优先级低，新运算符直接入栈
如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈
这个方法的时间复杂度为O(n)，整个字符串只需要扫描一遍。
运算符有+-*/()~^&都没问题，如果共有n个运算符，会有一个n*n的优先级表。
代码：
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
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;
if (p == '-') r = b - a;
if (p == '*') r = b * a;
if (p == '/') r = b / a;
num.push(r);//结果入栈
}
int main()
{
string s;//读入表达式
cin >> s;
for (int i = 0; i < s.size(); i++)
{
if (isdigit(s[i]))//数字入栈
{
int x = 0, j = i;//计算数字
while (j < s.size() && isdigit(s[j]))
{
x = x * 10 + s[j] - '0';
j++;
}
num.push(x);//数字入栈
i = j - 1;
}
//左括号无优先级，直接入栈
else if (s[i] == '(')//左括号入栈
{
op.push(s[i]);
}
//括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
else if (s[i] == ')')//右括号
{
while(op.top() != '(')//一直计算到左括号
eval();
op.pop();//左括号出栈
}
else
{
while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
eval();
op.push(s[i]);//操作符入栈
}
}
while (op.size()) eval();//剩余的进行计算
cout << num.top() << endl;//输出结果
return 0;
}
图片来自网络。
求个点赞~~
‘0’ 的 ASCII 码值是 48，‘1’ 的 ASCII 码值是 49，以此类推，所以减去 ‘0’ 的 ASCII 码值就可以得到数字本身。
假设 s = “123”，初始时 x = 0。
当 j = 0 时，x = x * 10 + (s[j] - ‘0’) = 0 * 10 + (1 - ‘0’) = 1，此时 j 自增，指向下一个字符。
当 j = 1 时，x = x * 10 + (s[j] - ‘0’) = 1 * 10 + (2 - ‘0’) = 12，此时 j 自增，指向下一个字符。
当 j = 2 时，x = x * 10 + (s[j] - ‘0’) = 12 * 10 + (3 - ‘0’) = 123。
最后得到 x = 123，即将字符串 “123” 转换成了整数 123。
牛逼
这里想了好久都没看懂，突然看到你这个，醍醐灌顶啊 哈哈哈
加上括号很好理解，%%%%
tql
哥们atoi就行了
是这样的，感谢解释。
这样很麻烦啊，直接用sscanf就能转换成数字了
今天再看的时候忽然觉得在比较新的操作符和栈顶操作符的时候，如果栈顶是‘（’是怎么处理的呀？h中没有设定左括号的优先级诶
应该是unordered_map里没有存储的，默认是0，优先级最低
好的，谢谢！
当你查询一个不存在在unordered_map里的key时，unordered_map会自动添加一个进去，由于int是built-in type，默认值是0，相当于在unordered_map里自动加入一个{“(“, 0};
醍醐灌顶
我认为核心思路就是：
第一步、把所有的括号先去掉，在去掉括号的情况下，表达式变得清爽不少
第二步、我们用栈来模拟运算，但是我们此时不能忽略op也就是算符的优先级，我们根据定义的优先级来决定什么时候先算什么时候不算
还有一点我们对优先级进行处理，op中算符的优先级是从小到大的
此时就类似于求后缀表达式的运算
你好，请问i=j-1是什么意思，我觉得应该是i=j
直接让i=j的话，循环结束
i会++；
这个懂了！
内层while循环会让j多加一位，for的块运行完后也会让i多加一位，这样就多加了两位，明显while多加的不能要
懂了，感谢
这是一个小型的双指针问题 可以看算法基础课第一章y总的讲解
谢谢
二刷感谢..
while(op.size() && op.top() != ‘(‘ && pr[op.top()] >= pr[c]) eval();
为什么这个里面的顺序不能变 ？
顺序一变就会Segmentation Fault
先判断栈是否为空，再进行取值。
&& 有短路原则，当栈空的时候，可以避免取值。
从空栈里取会报错
为什么去掉 op.top() != ‘(‘也对
一个月了，没看懂的东西首先就是来找小黄人hh
在编程和数据结构领域，stack（栈）是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。栈的主要操作包括push（压栈）、pop（弹栈）和top（查看栈顶
请问一下
while (op.size() && h[op.top()] >= h[s[i]])
这一句为什么不可以把两个判断条件倒过来写
我倒过来写报错了
先判断有效才能使用
这里面的while为什么不能用if
因为可能不止栈顶的运算符优先级>=待入栈的运算符。也就是说可能不止算一次。
这里用while而不用if的原因
因为可能栈顶的几个运算符中不止一个的运算符优先级>=待入栈的运算符。也就是说可能不止算一次。
j<=s.size()没有必要，显得多余
这个应该是必要的 不写上去容易死循环吧
你讲的是真他吗好，秒懂，服了
为什么while(op.size() && h[op.top()] >= h[ss[i]])可以AC而
while( h[op.top()] >= h[ss[i]] && op.size())就算编译错误呢？
y总代码while (op.size() && op.top() != ‘(‘ && pr[op.top()] >= pr[s[i]])这行里面
while条件里不写op.top() != ‘(‘ 也行吧?
因为(运算符优先级默认为0，不论什么时候它都不可能满足>=当前遍历运算符优先级的条件，即使出现表达式
((2+2)3)+5的情况，第二个(为当前遍历运算符时，满足pr[s.top()] == pr[s[i]]的条件，eval()什么也不执行。
错！假如表达式是2+23 + ((2+3) * 4)的情况时，第2个(为当前遍历的运算符时，eval()里不执行计算，但是num栈
里2和6出栈，op栈里第一个(出栈，这样莫名少了东西，但是没有任何计算，这样是错的吧。
所以，我觉得楼主写法可能应该不对，可能y总的数据里面没这种表达式，这样来说，y总的写法更严谨。
如果大家看出我的想法哪里错了，欢迎指正。
第一个举例表达式是((2+2) * 3) + 5,第二个表达式是2 + 2 * 3 + ((2+3) * 4)
错了，当前运算符是(的话，直接入op栈，没有第一个(和第二个(同级运算符的比较，
不会执行eval()。我举得第二个表示式例子是错误的。
楼主的写法是正确的，如(23+4),+为当前运算符时，计算23，将6入栈，此时op.top() == ‘(‘，由于
(的默认优先级为0，pr[op.top()] < pr[str[i[[ 一定严格成立，此时退出while循环，与遇到op栈顶为(就退出
while循环是一样的效果，所以y总的代码和楼主的都对，只不过楼主运用了(的默认优先级为0的隐藏条件。
漂亮
牛皮
请问用isdigit函数为啥不用加上ctype头文件？
牛逼大佬
大佬们，想问一下，就是最后对符号位操作的时候，那个op.size()为什么不能换成op.empty()呢
能换成!op.empty()