首页 > 代码库 > C++与数据结构 -- stack实现表达式求值[注释版]
C++与数据结构 -- stack实现表达式求值[注释版]
有好多朋友评论以前的那篇博文说:代码中间没有注释。由于课程一直比较紧张,所以答应的注释直到今天才写,
发表出来,与大家共享!
#include <map> #include <stack> #include <string> #include <iostream> #include <fstream> using namespace std; //为+,-,*,/运算符 设定优先级 map<char,int> priority; void initMap() { //+,-运算符的优先级低于*,/ priority.insert(make_pair(‘+‘,1)); priority.insert(make_pair(‘-‘,1)); priority.insert(make_pair(‘*‘,2)); priority.insert(make_pair(‘/‘,2)); } //为特定的运算符进行计算 int calculate(int a,char opera,int b) { int res = 0; switch(opera) { case ‘-‘: res = a - b; break; case ‘+‘: res = a + b; break; case ‘*‘: res = a * b; break; case ‘/‘: res = a / b; } return res; } //中缀表达式转后缀表达式 string infixToSuffix(const string &str) { stack<char> charStack; string ans; //返回值 for (string::const_iterator iter = str.begin(); iter != str.end(); ++iter) { if (isdigit(*iter)) //如果是数字,则直接输出[实际上是将其压入返回值] { ans.push_back(*iter); } else { //如果字符栈为空,或该字符为"(",或该运算符的优先级高于或等于栈顶元素,则进栈 if (charStack.empty() || *iter == ‘(‘ || priority[*iter] >= priority[charStack.top()]) { charStack.push(*iter); } //如果该字符为")",则将字符栈中的元素输出[放入到ans中],直到遇到"("为止 else if (*iter == ‘)‘) { while (charStack.top() != ‘(‘) { ans.push_back(charStack.top()); charStack.pop(); } charStack.pop(); //将栈顶的"("弹出 } //如果该运算符的优先级低于栈顶元素,则将栈中运算符持续输出, //直到遇到比该运算符优先级低的运算符为止 else if (priority[*iter] < priority[charStack.top()]) { while (!charStack.empty() && priority[charStack.top()] >= priority[*iter]) { ans.push_back(charStack.top()); charStack.pop(); } charStack.push(*iter); //将该运算符入栈 } } } //将栈中所剩余的运算符持续输出 while (!charStack.empty()) { ans.push_back(charStack.top()); charStack.pop(); } return ans; } //后缀表达式求值 int figureOut(const string &expr) { stack<int> intStack; for (string::const_iterator iter = expr.begin(); iter != expr.end(); ++iter) { //如果该元素为数字,则直接进入数字栈 if (isdigit(*iter)) { intStack.push((*iter - ‘0‘)); } //如果该元素是运算符,则将栈顶的两个元素取出,进行计算,将结果压入数字栈 else { char o = *iter; int a = intStack.top(); //取出栈顶元素 intStack.pop(); //删除栈顶元素 int b = intStack.top(); //取出栈顶元素 intStack.pop(); //删除栈顶元素 intStack.push(calculate(b,o,a)); //计算并入栈 } } return intStack.top(); //返回最终结果 } int main() { // freopen("input.txt","r",stdin); initMap(); //初始化运算符优先级 string expr; //中缀表达式 while (cin >> expr) { string suffix = infixToSuffix(expr); //后缀表达式 //删除栈顶元素 int ans = figureOut(suffix); cout << ans << endl; } } /**测试数据: * 9+8/4*(2+1)/2 * 9+(3-1)*3+8/2 **注意:该程序只能处理表达式中的数字只能为0~9, * 大于个位的数字无法处理! */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。