写点什么

算术四则混合运算表达式的求值

作者:可口也可樂
  • 2022-10-25
    湖南
  • 本文字数:2693 字

    阅读完需:约 9 分钟

@TOC


  • [问题]


利用算符优先关系,实现对算术四则混合运算表达式的求值


  • [要求]


  1. 输入的形式:表达式,例如 2*(3+4)

  2. 包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')';

  3. 输出的形式:运算结果,例如 2*(3+4)=14;

  4. 程序所能达到的功能:对表达式求值并输出


  • 思路:利用栈实现表达式求值,需要思考如下问题:


  1. 算符的优先级

  2. 字符转换成数字(包括解析小数)


  • 主要思路:


算术表达式有三种类型:前缀,中缀,后缀表达式,而这里主要利用的是中缀和后缀表达式


  • 示图:



  • 中缀表达式:运算符位于操作数中间


  1. 中缀表达式的运算规则:“先乘除,后加减,从左到右计算,先括号内,后括号外”

  2. 即中缀表达式不仅要依赖运算符优先级,而且还要处理括号


  • 后缀表达式:运算符在操作数的后面


  1. 已考虑了运算符的优先级,而且越放在前面的运算符来越优先执行

  2. 没有括号,只有操作数和运算符


我们平常使用的是中缀表达式,而后缀表达式运算的优先已经好了,所以我们用后缀表达式进行四则计算


  • 步骤一:中缀表达式转后缀表达式

  • 示图:





  • 过程实现:


  1. 遍历中缀表达式

  2. 遇到数字直接放入后缀表达式

  3. 遇到左括号入栈

  4. 遇到右括号则将栈里的运算符一直出栈到左括号出栈,并按出栈顺序放入后缀表达式中(达到一个去括号的效果)

  5. 遇到 * / 运算符,因为是较高优先级运算符,所以直接入栈

  6. 遇到 + - 运算符,因为是较低优先级运算符,所以需要先将栈顶高于或等于其优先级的运算符 * / 给出栈并放入后缀表达式中(遇到左括号需要停止)

  7. 遇到其他字符则直接报错退出程序

  8. 当遍历完后再将栈中剩余的运算符给出栈并放入后缀表达式中


  • 步骤二:依靠后缀表达式计算结果


因为后缀表达式已经达到去括号,决定运算符优先级的效果了,所以可以直接计算


  • 示图:



  • 过程实现:


  1. 遍历后缀表达式

  2. 遇到数字直接入栈

  3. 遇到运算符则将栈顶出栈,取出两个操作数(注:左操作数是第二个出栈的数值)

  4. 根据操作符将两操作数进行运算得到得结果给入栈到栈中

  5. 遍历结束后,栈顶的数据就是最后的结果


  • 思考:


  1. 优先级:后缀表达式已经将运算符的优先级给处理好了

  2. 字符转浮点:从中缀表达式转后缀时,遍历到数字或小数点则一直进行放入到后缀表达式中,并在最后放一个空格做分隔符,处理后缀表达式时遇到数字就依靠分隔符确定区间并转成浮点数


  • 实现代码:


#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<string>#include<stack>#include <stdlib.h>using namespace std;
string TransExpToPostexp(string& exp){ stack<char> optr; string postexp; for (int i = 0; i < exp.size(); i++) { if ((exp[i] >= '0' && exp[i] <= '9') || exp[i] == '.')//是数字直接进字符串 { postexp += exp[i]; while ((exp[i+1] >= '0' && exp[i+1] <= '9') || exp[i+1] == '.') postexp += exp[++i];
postexp += ' ';//分隔 } else { if (exp[i] == '(')//是左括号进栈 optr.push(exp[i]); else if (exp[i] == ')')//遇到右括号则出栈到左括号出栈 { while (!optr.empty()) { if (optr.top() == '(')//遇到左括号则出栈并退出 { optr.pop(); break; } else//遇到其他操作符则添加到后缀表达式中并出栈 { postexp += optr.top(); postexp += ' ';//分隔 optr.pop(); } } } else if (exp[i] == '*' || exp[i] == '/') { optr.push(exp[i]); } else if (exp[i] == '-' || exp[i] == '+') { while (!optr.empty()&&optr.top()!='(')//小于等于栈顶操作符数据,则出栈* { postexp += optr.top(); postexp += ' ';//分隔 optr.pop(); } //进栈 optr.push(exp[i]); } else//表达式错误 { perror("exp error!"); exit(1); } } } //遍历结束,剩余操作符出栈 while (!optr.empty()) { postexp += optr.top(); postexp += ' ';//分隔 optr.pop(); } return postexp;}

double Calculate(string postexp){ stack<double> data;//数据栈 for (int i = 0; i < postexp.size(); i++) { if (postexp[i] >= '0' && postexp[i] <= '9')//是数字则入栈 { int left = i, right = i; while (postexp[right] != ' ') right++; double num = atof(postexp.substr(left,right).c_str());//字符串转浮点 //cout << num << endl; data.push(num); i = right; } else//遇到操作符 { //取栈顶两数据,注意先后顺序,后一个才是左操作数 double right = data.top(); data.pop(); double left = data.top(); data.pop(); //判断操作符,得到数据再入栈 char optr = postexp[i]; switch (optr) { case '+': data.push(left + right); break; case '-': data.push(left - right); break; case '*': data.push(left * right); break; case '/': data.push(left / right); break; default: perror("optr error"); break; } cout << data.top() << endl; i++; } } return data.top();}
int main(){ string str; while (cin >> str) { string postexp=TransExpToPostexp(str) ; cout << postexp << endl; cout << Calculate(postexp) << endl; } return 0;}
复制代码


  • 测试:



发布于: 刚刚阅读数: 4
用户头像

还未添加个人签名 2022-04-28 加入

还未添加个人简介

评论

发布
暂无评论
算术四则混合运算表达式的求值_算法_可口也可樂_InfoQ写作社区