首页 > 代码库 > 中缀表达式求值 C++ Stack
中缀表达式求值 C++ Stack
给一个包含小数的中缀表达式 求出它的值
首先转换为后缀表达式然后利用stack求出值
转换规则:
如果字符为‘(‘ push
else if 字符为 ‘)‘
出栈运算符直到遇到‘(‘
else if 字符为‘+’,’-‘,’*‘,’/‘
{
if 栈为空或者上一个运算符的优先级小于当前运算符
push
else
{
运算符优先级小于等于栈顶运算符的优先级,出栈
然后!将当前运算符入栈!
}
}
代码
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<sstream> #include<algorithm> #include<queue> #include<deque> #include<iomanip> #include<vector> #include<cmath> #include<map> #include<stack> #include<set> #include<fstream> #include<memory> #include<list> #include<string> using namespace std; typedef long long LL; typedef unsigned long long ULL; #define MAXN 1100 #define L 31 #define INF 1000000009 #define eps 0.00000001 /* 1.000+2/4= ((1+2)*5+1)/4= 首先把中缀表达式转换为后缀表达式!(注意点运算符求值) 转换后的结果用一个string vector来表示 然后从前到后求值,pop两个数字 计算结果然后插入到stack中 */ string str; vector<string> trans; stack<char> S; stack<float> cal; map<char, int> pri; void Read() { string tmp; trans.clear(); while (!S.empty()) S.pop(); while (!cal.empty()) cal.pop(); for (int i = 0; i < str.size() - 1; i++)// 特殊考虑( ) . { if (str[i] == ‘(‘) { if (!tmp.empty()) { trans.push_back(tmp); tmp.clear(); } S.push(str[i]); } else if (str[i] == ‘)‘) { if (!tmp.empty()) { trans.push_back(tmp); tmp.clear(); } while (!S.empty() && S.top() != ‘(‘) { string ttt = ""; ttt.push_back(S.top()); trans.push_back(ttt); S.pop(); } if (!S.empty() && S.top() == ‘(‘) S.pop(); } else if (str[i] == ‘+‘ || str[i] == ‘-‘ || str[i] == ‘*‘ || str[i] == ‘/‘) { if (!tmp.empty()) { trans.push_back(tmp); tmp.clear(); } if (S.empty() || pri[S.top()]<pri[str[i]]) { S.push(str[i]); continue; } else { while (!S.empty() && pri[S.top()] >= pri[str[i]]) { string ttt = ""; ttt.push_back(S.top()); trans.push_back(ttt); S.pop(); } S.push(str[i]); } } else { tmp.push_back(str[i]); } } if (!tmp.empty()) { trans.push_back(tmp); tmp.clear(); } while (!S.empty()) { string ttt = ""; ttt.push_back(S.top()); trans.push_back(ttt); S.pop(); } } float solve()//计算转化出的后缀表达式的值 { while (!cal.empty()) cal.pop(); for (int i = 0; i < trans.size(); i++) { if (trans[i] == "+" || trans[i] == "-" || trans[i] == "*" || trans[i] == "/") { float a, b; a = cal.top(); cal.pop(); b = cal.top(); cal.pop(); if (trans[i] == "+") cal.push(a + b); else if (trans[i] == "-") cal.push(b - a); else if (trans[i] == "*") cal.push(a * b); else cal.push(b / a); } else { cal.push(atof(trans[i].c_str())); } } return cal.top(); } int main() { int n; cin >> n; pri[‘+‘] = pri[‘-‘] = 0, pri[‘*‘] = pri[‘/‘] = 1, pri[‘(‘] = pri[‘)‘] = -1; while (n--) { cin >> str; Read(); printf("%.2f\n",solve()); } return 0; }
中缀表达式求值 C++ Stack
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。