HJ50-四则运算：栈的运用、中缀表达式转后缀表达式并计算结果
文章目录
- 题目
- 一、分析
- 1.1表达式预处理
- 1.2中缀表达式转后缀
- 1.3 后缀表达式计算结果
- 二、答案
题目
一、分析
通过利用栈将中缀表达式转换为后缀表达式，在根据后缀表达式计算运算结果。由于包含负数操作数的情况，并且操作数位数不固定为1，因此，需要对输入的表达式进行预处理，将操作数和操作符进行分离，并且将大括号和中括号统一为小括号。
1.1表达式预处理
/// <summary>
/// 预处理表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>表达式</returns>
std::vector<std::string> pretreat(const std::string& data)
{std::string value = data;//->处理括号for (int i = 0; i < value.size(); i++){if (value[i] == '[' || value[i] == '{') value[i] = '(';if (value[i] == ']' || value[i] == '}') value[i] = ')';}//->处理负数,并将运算符与运算数拆分开value = '(' + value + ')'; int index = -1;std::vector<std::string> content;for (int i = 0; i < value.size(); i++){//->负数操作数的情况if (value[i] == '-' && (i - 1) >= 0 && value[i - 1] == '(' && (i + 1) < value.size() && value[i + 1] >= '0' && value[i + 1] <= '9'){index = i;continue;}//->非负数操作数else if (value[i] >= '0' && value[i] <= '9' && index == -1){index = i;}if ((value[i] < '0' || value[i] > '9') && index != -1){content.push_back(value.substr(index, i - index));index = -1;}if ((value[i] < '0' || value[i] > '9') && index == -1){content.push_back(value.substr(i, 1));}}return content;
}
1.2中缀表达式转后缀
1.2.1 对于中缀表达式A+B*(C-D)-E/F转后后缀表达式时，栈中数据变化情况如下。
1.2.2 栈内和栈外操作符的优先级如下。
std::map<std::string, int> isp = { {"#",0}, {"(",1}, {"*",5}, {"/",5}, {"+",3}, {"-",3}, {")",6} };//->栈内操作符的优先级
std::map<std::string, int> icp = { {"#",0}, {"(",6}, {"*",4}, {"/",4}, {"+",2}, {"-",2}, {")",1} };//->栈外操作符的优先级
1.2.3 代码逻辑伪代码如下，可根据此变化设计代码逻辑。
| 步 | 扫描项 | 项类型 | 动作 | 栈变化 | 输出 |
|---|---|---|---|---|---|
| 0 | “#”进栈 | # | |||
| 1 | A | 操作数 | # | A | |
| 2 | + | 操作符 | isp[“#”] < icp[“+”],进栈 | #+ | A |
| 3 | B | 操作数 | #+ | AB | |
| 4 | * | 操作符 | isp[“+”] < icp[“*”],进栈 | #+* | AB |
| 5 | ( | 操作符 | isp[“*”] < icp[“(”],进栈 | #+*( | AB |
| 6 | C | 操作数 | #+*( | ABC | |
| 7 | - | 操作符 | isp[“(”] < icp[“-”],进栈 | #+*(- | ABC |
| 8 | D | 操作数 | #+*(- | ABCD | |
| 9 | ) | 操作符 | isp[“-”] >icp[“)”],退栈 | #+*( | ABCD- |
| ”(“ == “)”,退栈 | #+* | ABCD- | |||
| 10 | - | 操作符 | isp[“*”] > icp[“-”],退栈 | #+ | ABCD-* |
| isp[“+”] > icp[“-”],退栈 | # | ABCD-*+ | |||
| isp[“#”] < icp[“-”],进栈 | #- | ABCD-*+ | |||
| 11 | E | 操作数 | #- | ABCD-*+E | |
| 12 | / | 操作符 | isp[“-”] < icp[“/”],进栈 | #-/ | ABCD-*+E |
| 13 | F | 操作数 | #-/ | ABCD-*+EF | |
| 14 | # | 操作符 | isp[“/”] > icp[“#”],退栈 | #- | ABCD-*+EF/ |
| 操作符 | isp[“-”] > icp[“#”],退栈 | # | ABCD-*+EF/- | ||
| 结束 |
/// <summary>
/// 判断是否是操作数
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
bool isDigit(std::string& value)
{if (value.empty())return false;return value.back() >= '0' && value.back() <= '9';
}/// <summary>
/// 将中缀表达式转换为后缀表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>后缀表达式</returns>
std::vector<std::string> postfix(std::vector<std::string>& content)
{//->定义栈内操作符和栈外操作符的优先级std::map<std::string, int> isp = { {"#",0}, {"(",1}, {"*",5}, {"/",5}, {"+",3}, {"-",3}, {")",6} };//->栈内操作符的优先级std::map<std::string, int> icp = { {"#",0}, {"(",6}, {"*",4}, {"/",4}, {"+",2}, {"-",2}, {")",1} };//->栈外操作符的优先级content.push_back("#");int index = 0;std::vector<std::string> expression;std::string item1 = "#", item2, item3;std::stack<std::string> stack;stack.push(item1);item1 = content[index];index++;while (!stack.empty() && item1 != "#"){if (isDigit(item1)){expression.push_back(item1);item1 = content[index];index++;}else{item2 = stack.top();if (isp[item2] < icp[item1]){stack.push(item1);item1 = content[index];index++;}else if (isp[item2] > icp[item1]){expression.push_back(stack.top());item3 = stack.top();stack.pop();}else{std::string item = stack.top();stack.pop();if (item == "("){item1 = content[index];index++;}}}}return expression;
}
1.3 后缀表达式计算结果
1.3.1 计算后缀表达式ABCD-*+EF/-栈中元素变化情况，逻辑如下。
| 步 | 扫描项 | 项类型 | 动作 | 栈中内容 |
|---|---|---|---|---|
| 1 | 栈置空 | 空 | ||
| 2 | A | 操作数 | 进栈 | A |
| 3 | B | 操作数 | 进栈 | AB |
| 4 | C | 操作数 | 进栈 | ABC |
| 5 | D | 操作数 | 进栈 | ABCD |
| 6 | - | 操作符 | D、C退栈，计算C-D，结果R1进栈 | ABR1 |
| 7 | * | 操作符 | R1、B退栈，计算B*R1，结果R2进栈 | BR2 |
| 8 | + | 操作符 | R2、B退栈，计算A+R2，结果R3进栈 | R3 |
| 9 | E | 操作数 | 进栈 | R3E |
| 10 | F | 操作数 | 进栈 | R3EF |
| 11 | / | 操作符 | F、E退栈，计算E/F，结果R4进栈 | R3R4 |
| 12 | - | 操作符 | R4、R3退栈。计算R3-R4，结果R5进栈 | R5 |
/// <summary>
/// 根据后缀表达式计算结果
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
float calculator(std::vector<std::string>& expression)
{std::stack<float> values;for (int i = 0; i < expression.size(); i++){std::string value = expression[i];if (isDigit(value)){values.push(std::atoi(value.c_str()));}else{float value1 = values.top(); values.pop();float value2 = values.top(); values.pop();switch (value[0]){case '+': values.push(value2 + value1); break;case '-': values.push(value2 - value1); break;case '*': values.push(value2 * value1); break;case '/': values.push(value2 / value1); break;default:break;}}}return values.top();
}
二、答案
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <map>/// <summary>
/// 判断是否是操作数
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
bool isDigit(std::string& value)
{if (value.empty())return false;return value.back() >= '0' && value.back() <= '9';
}/// <summary>
/// 将中缀表达式转换为后缀表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>后缀表达式</returns>
std::vector<std::string> postfix(std::vector<std::string>& content)
{//->定义栈内操作符和栈外操作符的优先级std::map<std::string, int> isp = { {"#",0}, {"(",1}, {"*",5}, {"/",5}, {"+",3}, {"-",3}, {")",6} };//->栈内操作符的优先级std::map<std::string, int> icp = { {"#",0}, {"(",6}, {"*",4}, {"/",4}, {"+",2}, {"-",2}, {")",1} };//->栈外操作符的优先级content.push_back("#");int index = 0;std::vector<std::string> expression;std::string item1 = "#", item2, item3;std::stack<std::string> stack;stack.push(item1);item1 = content[index];index++;while (!stack.empty() && item1 != "#"){if (isDigit(item1)){expression.push_back(item1);item1 = content[index];index++;}else{item2 = stack.top();if (isp[item2] < icp[item1]){stack.push(item1);item1 = content[index];index++;}else if (isp[item2] > icp[item1]){expression.push_back(stack.top());item3 = stack.top();stack.pop();}else{std::string item = stack.top();stack.pop();if (item == "("){item1 = content[index];index++;}}}}return expression;
}/// <summary>
/// 预处理表达式
/// </summary>
/// <param name="data">中缀表达式</param>
/// <returns>表达式</returns>
std::vector<std::string> pretreat(const std::string& data)
{std::string value = data;//->处理括号for (int i = 0; i < value.size(); i++){if (value[i] == '[' || value[i] == '{') value[i] = '(';if (value[i] == ']' || value[i] == '}') value[i] = ')';}//->处理负数,并将运算符与运算数拆分开value = '(' + value + ')'; int index = -1;std::vector<std::string> content;for (int i = 0; i < value.size(); i++){//->负数操作数的情况if (value[i] == '-' && (i - 1) >= 0 && value[i - 1] == '(' && (i + 1) < value.size() && value[i + 1] >= '0' && value[i + 1] <= '9'){index = i;continue;}//->非负数操作数else if (value[i] >= '0' && value[i] <= '9' && index == -1){index = i;}if ((value[i] < '0' || value[i] > '9') && index != -1){content.push_back(value.substr(index, i - index));index = -1;}if ((value[i] < '0' || value[i] > '9') && index == -1){content.push_back(value.substr(i, 1));}}return content;
}/// <summary>
/// 根据后缀表达式计算结果
/// </summary>
/// <param name="expression"></param>
/// <returns></returns>
float calculator(std::vector<std::string>& expression)
{std::stack<float> values;for (int i = 0; i < expression.size(); i++){std::string value = expression[i];if (isDigit(value)){values.push(std::atoi(value.c_str()));}else{float value1 = values.top(); values.pop();float value2 = values.top(); values.pop();switch (value[0]){case '+': values.push(value2 + value1); break;case '-': values.push(value2 - value1); break;case '*': values.push(value2 * value1); break;case '/': values.push(value2 / value1); break;default:break;}}}return values.top();
}int main()
{std::string data;std::cin >> data;std::vector<std::string> content = pretreat(data);std::vector<std::string> expression = postfix(content);std::cout << calculator(expression);return 0;
}