个人主页：仍有未知等待探索_C语言疑难,数据结构,算法-CSDN博客
专题分栏：算法_仍有未知等待探索的博客-CSDN博客
目录
一、前言
二、解析
分析
最后直接上代码！
一、前言
表达式求值是一个比较基础的代码关于栈的使用。在写的时候充分锻炼了大脑的思维和对代码的调试能力。
如果是在纸上给一个计算表达式，你一定可以算出来，但是要用代码实现的时候就会感觉没什么思路了，接下来就来看我给你“操作一番”！
二、解析
分析
首先，从比较简单的表达式开始，看这个表达式是如何进行计算的。
一开始，我们需要两个栈，一个用来存储操作数，另外一个用来存储运算符栈。
表达式用一个string类型进行存储（c语言的话，用一个char类型的数组也行）。然后依次遍历每个元素。
- 先判断这个元素是不是数字，如果是的话，就直接进操作数栈。
- 如果这个元素是左括号的话‘（ ’ 就直接进入符号栈（括号的优先级比普通的运算符高）
- 如果这个元素是右括号的话‘）’ 就依次把计算（也就是操作数栈弹出两个数，符号栈弹出一个符号）直到符号栈的栈顶是左括号，把左括号出栈，然后结束循环。
- 如果这个元素是普通符号的话，就需要判断一下符号的优先级，如果要入栈的符号优先级高的话，就直接压栈；否则就是先计算然后再进行压栈。
- 最后就是计算剩在栈里面的数，直到符号栈为空，操作数栈只剩一个数。然后把这个数输出来就行。
最后直接上代码！
#include <iostream>
using namespace std;
#include <stack>
#include <unordered_map>
#include <string>
stack<int>num;
stack<char>op;
string str;
// 存储运算符的优先级，等价于将一个；‘+’ == 1
unordered_map<char, int>pr = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };
// 计算函数
void eval()
{
// 从操作数栈弹出两个数，弹出的第一个数是双目操作符右边的数，要注意
int a = num.top(); num.pop();
int b = num.top(); num.pop();
// 从符号栈弹出一个符号
char opp = op.top(); op.pop();
// 计算
int c = 0;
if (opp == '+') c = b + a;
else if (opp == '-') c = b - a;
else if (opp == '*') c = b * a;
else if (opp == '/') c = b / a;
// 将得数进行压栈操作
num.push(c);
}
int main()
{
// C++ 输入输出的加速语句
std::ios::sync_with_stdio(false);
cin.tie(0);
// 读入表达式
cin >> str;
for (int i = 0; i < str.size(); i++)
{
// auto 是一个关键字，系统可以根据后面赋值的数据类型自动进行匹配类型
auto c = str[i];
// 判断这个字符是不是数字
if (isdigit(c))
{
auto j = i;
int x = 0;
// 如果这个数字的后面还是数字的话，证明数字不止一位，要进行加权操作
while (j < str.size() && isdigit(str[j]))
{
x = x * 10 + str[j] - '0';
j++;
}
// 将i移到j - 1的位置上，因为j在最后一个循环中+1操作了
// j的位置现在是在相当于第一个不是数字的位置上，然后这个判断语句结束后，
// i会继续+1，所以i要移到j前一个位置上，来让下一个循环到指定的位置上
i = j - 1;
num.push(x);
}
else if (c == '(') op.push(c);// 遇到左括号直接压栈
else if (c == ')')// 遇到右括号，计算到符号栈栈顶是左括号，然后左括号出栈
{
while (op.size() && op.top() != '(') eval();
op.pop();
}
else// 一般情况，注意一定是while循环，不懂的可以去搜一下表达式树，方便理解
{
while (op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
// 处理最后栈里的元素
while (op.size()) eval();
// 输出栈顶元素
cout << num.top() << endl;
return 0;
}
