算法思想

这是对栈的应用，对于中缀表达式求值，需要定义两个栈：数字栈和符号栈，顾名思义分别存放数字和符号。

遇到数字，直接入数字栈，需要注意并不是只有个位数，还是需要一定的处理，详情见代码。
遇到符号，有三种情况：

左括号(：直接入符号栈。
右括号)：取两个数字栈的数据，取一个符号栈的数据，计算结果放入数字栈，循环直到符号栈中取出(结束。
+-*/运算符：符号栈为空，直接入符号栈，不为空则需要比较当前的运算符和符号栈栈顶元素的优先级，当栈顶元素优先级大于等于当前的运算符，符号栈出栈，取两个数字栈元素进行计算，结果放入数字栈，循环，将所有大于等于当前的运算符的全部出栈为止。

最后的计算结果为数字栈的栈顶元素。

提前使用map集合定义好优先级

代码实现

#include 
#include 
#include 
#include using namespace std;// 表达式求值 1+2*3/4*(5-6)int main() {string str; // 表达式stack num; // 数字栈stack ch; // 符号栈// 定义好运算符的优先级 括号优先级为 0 map 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;
}

上面代码有一段多次重复的代码，最好重构一下，单独拿出来封装成一个方法。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：玩家实测“九九联盟能不能开透视挂”(真的有挂)

下一篇：我来分享.朋友安徽麻将能不能开挂.辅助神器下载!

【C++】表达式求值

文章目录

算法思想

代码实现

相关内容

热门资讯