文章目录
- 算法思想
- 代码实现
算法思想
这是对栈的应用,对于中缀表达式求值,需要定义两个栈:数字栈和符号栈,顾名思义分别存放数字和符号。
- 遇到数字,直接入数字栈,需要注意并不是只有个位数,还是需要一定的处理,详情见代码。
- 遇到符号,有三种情况:
- 左括号
(
:直接入符号栈。 - 右括号
)
:取两个数字栈的数据,取一个符号栈的数据,计算结果放入数字栈,循环直到符号栈中取出(
结束。 +-*/
运算符:符号栈为空,直接入符号栈,不为空则需要比较当前的运算符
和符号栈栈顶元素
的优先级,当栈顶元素优先级大于等于
当前的运算符,符号栈出栈,取两个数字栈元素进行计算,结果放入数字栈,循环,将所有大于等于
当前的运算符的全部出栈为止。
- 最后的计算结果为数字栈的栈顶元素。
提前使用map集合定义好优先级
代码实现
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
// 表达式求值 1+2*3/4*(5-6)
int main() {
string str; // 表达式
stack<int> num; // 数字栈
stack<char> ch; // 符号栈
// 定义好运算符的优先级 括号优先级为 0
map<char, int> m;
m['+'] = 1;
m['-'] = 1;
m['/'] = 2;
m['*'] = 2;
m['('] = 0;
m[')'] = 0;
int a, b, i, sum;
while (cin >> str)
{
i = 0;
while (i < str.size())
{
// 遇到数字 直接入栈
if (str[i] <= '9' && str[i] >= '0') {
sum = 0;
while (str[i] <= '9' && str[i] >= '0') {
sum = sum * 10 + (str[i] - '0');
i++;
}
num.push(sum);
}
else
{
// 遇到符号
// 左括号 直接入栈
if (str[i] == '(') {
ch.push(str[i]);
}
else if (str[i] == ')')
{
// 右括号: 符号位要一直出栈,直到, 第一个(出现
while (ch.top() != '(') {
a = num.top();
num.pop();
b = num.top();
num.pop();
switch (ch.top())
{
case('+'): a = a + b; break;
case('-'): a = b - a; break;
case('*'): a = a * b; break;
case('/'): a = b / a; break;
default:
break;
}
num.push(a);
ch.pop();
}
ch.pop(); // 左括号弹出
}
else
{
// 运算符 : 比较优先级 大于等于-》出栈计算 (循环)
while ( !ch.empty() && m[ch.top()] >= m[str[i]]) {
a = num.top();
num.pop();
b = num.top();
num.pop();
switch (ch.top())
{
case('+'): a = a + b; break;
case('-'): a = b - a; break;
case('*'): a = a * b; break;
case('/'): a = b / a; break;
default:
break;
}
num.push(a);
ch.pop();
}
ch.push(str[i]);
}
i++;
}
}
while (!ch.empty()) {
a = num.top();
num.pop();
b = num.top();
num.pop();
switch (ch.top())
{
case('+'): a = a + b; break;
case('-'): a = b - a; break;
case('*'): a = a * b; break;
case('/'): a = b / a; break;
default:
break;
}
num.push(a);
ch.pop();
}
cout << num.top() << endl;
}
return 0;
}
上面代码有一段多次重复的代码,最好重构一下,单独拿出来封装成一个方法。