首页 > 代码库 > 中缀表达式求解
中缀表达式求解
问题描述：
中缀表达式计算，只包含加减乘除以及括号，例如：
2+3*4-5/2 = 11.5
((2+3*4)-5)/2 = 4.5
思路：
1. 维护两个栈空间：数字栈与符号栈
2. 注意入栈与出栈的规则，符号栈入栈时，根据符号优先级判断是否入栈或出栈。
高优先级符号后入栈时直接放入即可，低优先级符号后入栈时先弹出高优先级符号，优先级如下：
( < +- < * / < )
普通操作符弹出计算时，只进行一次pop_cal操作。
右括号出栈时，必须循环计算至左括号出栈为止。
边界case：
1. 分母为0，assert处理。
2. 数字范围超出变量上下限。
知识点：
1. 栈操作：围绕出栈入栈操作分解问题，分解成cal计算函数、push_xxx压栈操作、pop_cal出栈计算操作、push_check入栈检查优先级等几步，逻辑会更清晰。
2. 字符处理：用stringstream简化处理逻辑，string -> float, float -> string，多次使用之间需要clear() & str("")，重置标识以及清空字符串两个操作。
难度：★★★★
1. 代码量大
2. 需要考虑的细节多：字符处理、边界case、符号优先级、右括号特殊处理
3. 熟悉栈操作
伪码：
1 #include <stack> 2 #include <string> 3 #include <sstream> 4 #include <iostream> 5 #include <assert.h> 6 #include <ctype.h> 7 8 using namespace std; 9 10 stack<string> nums; //数字栈11 stack<char> exps; //操作符栈12 13 //主函数：计算中缀表达式14 float cal_res(const string &express)15 {16 //是否新数字17 bool new_num = true;18 //循环读取表达式字符19 for(size_t i = 0; i < express.size(); i++) 20 {21 //处理数字22 if( isdigit( express[i] ) )23 {24 //数字压栈25 push_num(express[i], new_num);26 new_num = false;27 }28 else29 {30 //操作符压栈31 push_exp( express[i] );32 new_num = true;33 }34 }35 //循环出栈，计算结果36 float res = 0.0;37 while( exps.size() > 0 )38 {39 pop_cal( res );40 }41 return res;42 }43 44 //压入数字栈45 void push_num(char exp, bool new)46 {47 //...48 }49 50 //压入操作符栈51 void push_exp(char exp)52 {53 //...54 }55 56 //检查入栈优先级57 bool push_check(char exp)58 {59 //...60 }61 62 //出栈一次并计算结果，返回当前出栈操作符63 char pop_cal(float &res)64 {65 //...66 }
转载请注明引用自：
http://www.cnblogs.com/breakthings/p/4049575.html
中缀表达式求解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。