简介
此模块为学校数据结构必修课学习内容的记录与分享
全文大体分为一下几个部分
- 前言
- 背景
- 分析（伪代码部分）
- 代码
- 结果
- Points
前言
由于前段时间赶团队培训进度，后面需要对培训内容进行总结，因此以后相当一部分时间在 homework 上面的时间可能会减少，因此先贴出主要思路及要点，后面抽时间进行细节补充与整理
又挖坑了…QAQ
背景
利用栈的后进先出特点对表达式求值进行处理
此可看作括号匹配的Plus版本
分析：
需要两个栈，一个数据栈，一个操作符栈
根据操作符号里的优先级判断决定是否将操作数弹栈进行计算
代码
//202031061018 刘知鑫
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
void eval()
{
auto b = num.top();
num.pop();
auto a = num.top();
num.pop();
auto c = op.top();
op.pop();
int x;
if (c == '+') x = a + b;
else if (c == '-') x = a - b;
else if (c == '*') x = a * b;
else x = a / b;
num.push(x);
}
int main()
{
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
string str;
cin >> str;
for (int i = 0; i < str.size(); i ++ )
{
auto c = str[i];
if (isdigit(c))
{
int x = 0, j = i;
while (j < str.size() && isdigit(str[j]))
x = x * 10 + str[j ++ ] - '0';
i = j - 1;
num.push(x);
}
else if (c == '(') op.push(c);
else if (c == ')')
{
while (op.top() != '(') eval();
op.pop();
}
else
{
while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while (op.size()) eval();
cout << num.top() << endl;
return 0;
}
结果
#include <iostream>
#include <unordered_map>
#include <cstring>
#include <stack>
#include <stdio.h>
using namespace std;
/*定义全局栈*/
stack<double> num;//数据栈
stack<char> op;//运算符栈
void arithmetic()
{
auto first_num = num.top();//取出栈顶元素
num.pop();//更新栈顶元素
auto second_num = num.top();//取出第二个栈顶元素
num.pop();//更新栈顶
auto operation_symbol = op.top();//取出栈顶运算符
op.pop();
double sum = 0;
switch (operation_symbol)
{
case '+':
sum = second_num + first_num;
break;
case '-':
sum = second_num - first_num;
break;
case '*':
sum = second_num * first_num;
break;
case '/' :
sum = second_num / first_num;
break;
default:
break;
}
num.push(sum);
}
void Test()
{
//运算符容器。‘+’对应数字1，类似于ASCII码值的对应
unordered_map<char, int> Operator
{
{'+',1},{'-',1},{'*',2},{'/',2}
};
string str;
cout << "请输入表达式 (负数表示为:(0-a))" << endl;
cin >> str;
int flag = 1;//负数的处理
for (int i = 0; i < str.size(); i++)
{
auto c = str[i];
if (isdigit(c))
{
double data = 0;
int j = i;
while (j < str.size() && isdigit(str[j])&&str[j]!='.')
{
data = data * 10 + str[j++] - '0';//由于定义输入的是string类型，涉及到强制转换，数字字符减去‘0’，
//经过ASCII码值的转换就是对应的十进制数字
}
if (str[j] == '.')
{
j++;
int power = -1;
while (isdigit(str[j]))
{
data = data + (str[j] - '0') * pow(10,power);
j++;
power--;
}
}
i = j-1;//退出循环，说明j下标对应的不是数字了，退一位，是因为i在for循环要i++,无次-1操作就会出现，i的两次跳跃
num.push(data*flag);
flag = 1;
}
else if (c == '(')
{
op.push(c);
if (str[i + 1] == '-')
{
flag = -1;
i++;
}
else
flag = 1;
}
else if (c == ')')
{
while (op.top() != '(')//进入该循环是在处理括号内部的计算
{
arithmetic();
}
op.pop();
}
else//运算符压栈
{
if (c != '+' && c != '-' && c != '*' && c != '/')
{
cout << "非法输入!!!"<<endl;
return;
}
while (op.size() && op.top() != '(' && Operator[op.top()] >= Operator[c])
{
arithmetic();
}
op.push(c);
}
}
while (op.size())//只要还有运算符就说明没有结束运算
{
arithmetic();
}
cout <<"结果为:"<< num.top() << endl<<endl;
}
int main()
{
Test();
system("pause");
return 0;
}Points
后缀表达式
注意：
后缀表达式不是必须操作数和操作符分开，例如：3 4 + 2 * 也算是后缀表达式
利用栈对表达式求值的核心就是将操作符和操作数压入栈内，形成“后缀表达式”，在利用后缀表达式的求值特点，一次次弹栈计算结果，最后得到最终答案
什么是后缀表达式
后缀表达式也叫逆波兰表达式，是一种数学表达式的表示方法 ，具有独特的表示形式、运算规则和应用优势。
与常见的中缀表达式（操作符在操作数中间，如a+b ）不同，后缀表达式将操作符放在操作数的后面 。比如，中缀表达式3+4∗2写成后缀表达式是342∗+ ；中缀表达式(3+4)∗2的后缀表达式为34+2∗ 。它通过操作数在前、操作符紧跟其后的方式，消除了括号对运算顺序的显式表达 ，让计算机能更直接明确运算顺序。
运算规则
计算后缀表达式时，从左到右遍历表达式：
- 遇到操作数：将其压入栈中 。例如遍历342∗+时，先遇到3，将3压入栈；再遇到4，把4也压入栈 。
- 遇到操作符：从栈顶弹出所需数量的操作数进行计算（通常二元操作符弹出两个，一元操作符弹出一个 ），然后将计算结果重新压入栈中 。比如在342∗+中，遇到2时压入栈，接着遇到∗ ，从栈顶弹出2和4 ，计算4∗2=8 ，再把8压入栈；之后遇到+ ，弹出8和3 ，计算3+8=11 ，将11压入栈 。遍历完整个表达式后，栈中剩下的唯一元素就是表达式的计算结果 。
转换方法
通常可利用栈将中缀表达式转换为后缀表达式 ，步骤如下：
- 准备一个操作符栈和一个用于输出后缀表达式的结果栈 。
- 从左到右遍历中缀表达式：
- 若遇到操作数，直接将其添加到结果栈 。
- 若遇到操作符：
- 当操作符栈为空，直接将该操作符压入操作符栈 。
- 若操作符栈不为空，比较该操作符与操作符栈栈顶操作符的优先级 。若当前操作符优先级高，将其压入操作符栈；若当前操作符优先级低或相等，从操作符栈中弹出操作符并添加到结果栈，重复比较直至当前操作符能压入操作符栈 。
- 若遇到左括号，直接压入操作符栈 。
- 若遇到右括号，将操作符栈中的操作符弹出并添加到结果栈，直到遇到左括号（左括号弹出但不加入结果栈 ）。
- 遍历完中缀表达式后，将操作符栈中剩余的操作符依次弹出并添加到结果栈 ，此时结果栈中的内容就是对应的后缀表达式 。 例如中缀表达式3+4∗2 ，操作数3、4先入结果栈 ，遇到∗ ，因其优先级高于+ ，∗入操作符栈；再遇到2 ，2入结果栈；最后遇到+ ，∗出操作符栈进入结果栈 ，+入操作符栈 ，遍历结束后+出栈进入结果栈 ，得到后缀表达式342∗+ 。
注意：左括号也是运算符，并且是优先级最低的运算符
例子：
(a + [ b + ( c + d ) * e ] + f ) + g – h
转化过程
步骤分析
- 初始化：
- 准备一个空栈用于存放运算符。
- 准备一个空列表用于存储后缀表达式。
- 遍历中缀表达式：
- 遇到左括号
(或[时，将其压入栈中。 - 遇到操作数（如
a、b、c等）时，直接添加到后缀表达式列表中。 - 遇到运算符时，若栈为空或栈顶是左括号，则将运算符压入栈；若运算符优先级高于栈顶运算符，则压入栈；若优先级低于或等于栈顶运算符，则弹出栈顶运算符添加到后缀表达式列表，再比较新栈顶运算符，直到满足条件后将当前运算符压入栈。
- 遇到右括号
)或]时，将栈顶运算符弹出并添加到后缀表达式列表，直到遇到对应的左括号（左括号弹出但不添加到后缀表达式）。
- 遇到左括号
- 遍历结束：将栈中剩余的运算符依次弹出并添加到后缀表达式列表。
转换过程
遍历结束，将栈中剩余的运算符 - 弹出添加到后缀表达式，此时栈为 []，后缀表达式为 [a, b, c, d, +, e, *, +, f, +, g, +, h, -]。
遇到左括号 (，将其压入栈，此时栈为 [(]，后缀表达式为 []。
遇到操作数 a，将其添加到后缀表达式，此时栈为 [(]，后缀表达式为 [a]。
遇到运算符 +，将其压入栈，此时栈为 [(, +]，后缀表达式为 [a]。
遇到左括号 [，将其压入栈，此时栈为 [(, +, []，后缀表达式为 [a]。
遇到操作数 b，将其添加到后缀表达式，此时栈为 [(, +, []，后缀表达式为 [a, b]。
遇到运算符 +，将其压入栈，此时栈为 [(, +, [, +]，后缀表达式为 [a, b]。
遇到左括号 (，将其压入栈，此时栈为 [(, +, [, +, (]，后缀表达式为 [a, b]。
遇到操作数 c，将其添加到后缀表达式，此时栈为 [(, +, [, +, (]，后缀表达式为 [a, b, c]。
遇到运算符 +，将其压入栈，此时栈为 [(, +, [, +, (, +]，后缀表达式为 [a, b, c]。
遇到操作数 d，将其添加到后缀表达式，此时栈为 [(, +, [, +, (, +]，后缀表达式为 [a, b, c, d]。
遇到右括号 )，将栈顶运算符 + 弹出添加到后缀表达式，再弹出左括号 (，此时栈为 [(, +, [, +]，后缀表达式为 [a, b, c, d, +]。
遇到操作数 e，将其添加到后缀表达式，此时栈为 [(, +, [, +]，后缀表达式为 [a, b, c, d, +, e]。
遇到运算符 *（题目中省略乘号，这里按乘法处理），由于 * 优先级高于栈顶的 +，将 * 压入栈，此时栈为 [(, +, [, +, *]，后缀表达式为 [a, b, c, d, +, e]。
遇到右括号 ]，将栈顶运算符 * 和 + 依次弹出添加到后缀表达式，再弹出左括号 [，此时栈为 [(, +]，后缀表达式为 [a, b, c, d, +, e, *, +]。
遇到操作数 f，将其添加到后缀表达式，此时栈为 [(, +]，后缀表达式为 [a, b, c, d, +, e, *, +, f]。
遇到右括号 )，将栈顶运算符 + 弹出添加到后缀表达式，再弹出左括号 (，此时栈为 []，后缀表达式为 [a, b, c, d, +, e, *, +, f, +]。
遇到运算符 +，将其压入栈，此时栈为 [+]，后缀表达式为 [a, b, c, d, +, e, *, +, f, +]。
遇到操作数 g，将其添加到后缀表达式，此时栈为 [+]，后缀表达式为 [a, b, c, d, +, e, *, +, f, +, g]。
遇到运算符 -，由于 - 和 + 优先级相同，弹出 + 添加到后缀表达式，再将 - 压入栈，此时栈为 [-]，后缀表达式为 [a, b, c, d, +, e, *, +, f, +, g, +]。
遇到操作数 h，将其添加到后缀表达式，此时栈为 [-]，后缀表达式为 [a, b, c, d, +, e, *, +, f, +, g, +, h]。
最终结果：
a b c d + e * + f + g + h –
额，自己抄一遍，不要直接使用刘知鑫的代码。
好的好的，后面会抽出时间去复现代码的