个人主页：仍有未知等待探索_C语言疑难,数据结构,算法-CSDN博客

专题分栏：算法_仍有未知等待探索的博客-CSDN博客

目录

一、前言

二、解析

分析

最后直接上代码！

---

一、前言

表达式求值是一个比较基础的代码关于栈的使用。在写的时候充分锻炼了大脑的思维和对代码的调试能力。

如果是在纸上给一个计算表达式，你一定可以算出来，但是要用代码实现的时候就会感觉没什么思路了，接下来就来看我给你“操作一番”！

二、解析

分析

首先，从比较简单的表达式开始，看这个表达式是如何进行计算的。

 一开始，我们需要两个栈，一个用来存储操作数，另外一个用来存储运算符栈。

表达式用一个string类型进行存储（c语言的话，用一个char类型的数组也行）。然后依次遍历每个元素。

1. 先判断这个元素是不是数字，如果是的话，就直接进操作数栈。
2. 如果这个元素是左括号的话‘（ ’ 就直接进入符号栈（括号的优先级比普通的运算符高）
3. 如果这个元素是右括号的话‘）’ 就依次把计算（也就是操作数栈弹出两个数，符号栈弹出一个符号）直到符号栈的栈顶是左括号，把左括号出栈，然后结束循环。
4. 如果这个元素是普通符号的话，就需要判断一下符号的优先级，如果要入栈的符号优先级高的话，就直接压栈；否则就是先计算然后再进行压栈。
5. 最后就是计算剩在栈里面的数，直到符号栈为空，操作数栈只剩一个数。然后把这个数输出来就行。

最后直接上代码！

#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;
}