龍進记得去年刚上大一的时候，有一次实验课的作业就是做一个计算器。我当时就是想实现计算任意的四则运算表达式的功能。我依稀记得当时的实现非常的复杂，还用了正则表达式去匹配，获得相应的元素。但是当时没能实现处理括号的问题，只要不包含括号的算式，我当时都能解决。当时真的是想破脑袋都没想出来怎么解决这个问题。
然后直到现在看到数据结构这本书上面讲了，我才明白，赶紧按照书上的思路自己敲个代码来试试看。
逆波兰表达式
逆波兰表达式也称为后缀表达式，简单但不完全正确的说，就是把符号移到数字的后面。其实准确的说是遇到数字就压入栈，遇到符号就把栈顶的两个元素给弹出来，然后应用相应的计算过程，再把结果压入栈，直到最后就可以得到最终结果（最终状态下的栈顶元素，此时栈大小为1）
比如：4.99*1.06+5.99+6.99*1.06的逆波兰表达式是4.99 1.06 * 5.99 + 6.99 1.06 * +
将普通表达式转为逆波兰表达式
我们发现逆波兰表达式的计算过程非常简单，那么我们怎么把普通表达式转为逆波兰表达式呢？
方法：创建一个队列和一个栈。
遇到数字就压入队列，遇到符号就入栈。
对于符号的处理，有以下规则：
- 括号特殊处理，正括号优先级最高，副括号优先级最低，遇到副括号就往回找正括号。
- 其他符号根据优先级，若栈顶元素的优先级大于等于当前符号的优先级，且不是正括号 ==》 一直弹出，直到栈顶元素优先级比当前符号的低，然后把当前元素压入栈
弹出的符号除了括号外，都压入队列。
最终从依次队列首部取出元素，得到的就是逆波兰表达式了。
这很简单，看代码就行了。
代码：
#include <iostream>
#include<stack>
#include "string"
#include "sstream"
#include<queue>
#include "map"
using namespace std;
map<char, int> mp;
void init_priority() {
//定义优先级
mp['('] = 3;
mp[')'] = 0;
mp['+'] = mp['-'] = 1;
mp['*'] = mp['/'] = 2;
}
//截取字符串
string sub_str(const string &s, int st, int end) {
stringstream ss;
for (int i = st; i <= end; ++i)
ss << s[i];
string tmp = ss.str();
//cout<<tmp<<endl;
return tmp;
}
//生成逆波兰表达式
/**
* 数字直接加入表达式
* 符号入栈规则：
* 1、括号特殊处理，正括号优先级最高，副括号优先级最低，遇到副括号就往回找正括号。
* 2、其他符号根据优先级，若栈顶元素的优先级大于等于当前符号的优先级，且不是正括号 ==》 一直弹出，直到栈顶元素优先级比当前符号的低，
* 然后把当前元素压入栈
* @param s
* @return
*/
queue<string> generate_expression(string s) {
stack<char> stk;
queue<string> expression;//逆波兰表达式存储在这里
int last_idx = 0;
stringstream ss;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
if (last_idx <= i - 1)
expression.push(sub_str(s, last_idx, i - 1));
stk.push(s[i]);
last_idx = i + 1;
} else if (s[i] == ')') {
if (last_idx <= i - 1)
expression.push(sub_str(s, last_idx, i - 1));
while (!stk.empty() && stk.top() != '(') {
ss << stk.top();
expression.push(ss.str());
ss.clear();
ss.str("");
stk.pop();
}
stk.pop();
last_idx = i + 1;
} else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
if (last_idx <= i - 1)
expression.push(sub_str(s, last_idx, i - 1));
if (!stk.empty() && mp[s[i]] <= mp[stk.top()] && stk.top() != '(') {
while (!stk.empty() && mp[s[i]] <= mp[stk.top()] && stk.top() != '(') {
ss << stk.top();
expression.push(ss.str());
ss.clear();
ss.str("");
stk.pop();
}
}
stk.push(s[i]);
last_idx = i + 1;
}
}
int dis = s.length() - last_idx - 1;
if (dis >= 0) {
expression.push(sub_str(s, last_idx, s.length() - 1));
}
while (!stk.empty()) {
ss << stk.top();
expression.push(ss.str());
ss.clear();
ss.str("");
stk.pop();
}
return expression;
}
pair<double, double> get_num(stack<double> &stk) {
double a, b;
a = stk.top(), stk.pop();
b = stk.top(), stk.pop();
return make_pair(a, b);
}
double calculate(queue<string> expression) {
double ans = 0;
stack<double> stk;
bool err_flag = false;
while (!expression.empty()) {
if (expression.front() == "+") {
if (stk.size() < 2) {
err_flag = true;
break;
}
auto p = get_num(stk);
stk.push(p.first + p.second);
} else if (expression.front() == "-") {
if (stk.size() < 2) {
err_flag = true;
break;
}
auto p = get_num(stk);
stk.push(p.first - p.second);
} else if (expression.front() == "*") {
if (stk.size() < 2) {
err_flag = true;
break;
}
auto p = get_num(stk);
stk.push(p.first * p.second);
} else if (expression.front() == "/") {
if (stk.size() < 2) {
err_flag = true;
break;
}
auto p = get_num(stk);
stk.push(p.second / p.first);
} else {
//压入数字
stk.push(atof(expression.front().c_str()));
}
expression.pop();
}
if (err_flag || stk.size() != 1) {
cout << "表达式存在错误！" << endl;
exit(0);
} else
return stk.top();
}
int main() {
//初始化运算符的优先级
init_priority();
cout << "请输入算式：\n>> ";
string s;
cin >> s;
queue<string> expression = generate_expression(s);
queue<string> tmp = expression;
cout << "逆波兰表达式：";
while (!tmp.empty()) {
cout << tmp.front() << ' ';
tmp.pop();
}
cout << endl;
cout << "结果：" << calculate(expression) << endl;
return 0;
}转载请注明来源：https://www.longjin666.top/?p=1165
欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~
