后缀表达式转中缀表达式

发布时间:2014-10-25 2:20:41
来源:分享查询网

利用栈实现四则运算的后缀表达式转中缀表达式 本来想用stringstream,但在判断字符是操作数还是操作符的时候,挣扎了很久,都没弄出来。 似乎无法正确判断到是加运算符还是double数字之前的加号,最后还是用了比较熟悉的sscanf。也许是没用过C++开发项目,熟悉的依旧是C的函数~ 也尝试使用递归方法去做(觉得用递归代码也许会少点),没能成功,放弃了...  #include <iostream> #include <string> #include <stack> using namespace std; /* 运算符类,含符号和优先级,目前只支持四则运算 */ struct exp_symbol{ char op; int priority; exp_symbol(char op=0) { this->op = 0; priority = 255; if( '+' == op || '-' == op ) { this->op = op; priority = 1; } else if( '*' == op || '/' == op ) { this->op = op; priority = 2; } } exp_symbol(const exp_symbol &sym):op(sym.op),priority(sym.priority){ } friend bool operator < (const exp_symbol &l_sym, const exp_symbol &r_sym) { return (l_sym.priority < r_sym.priority) ? true : false; } exp_symbol & operator = (const exp_symbol &r_sym) { if( this != &r_sym ) { op = r_sym.op; priority = r_sym.priority; } return *this; } }; /* 表达式类,表达式字符串和运算符构成 */ struct expression{ string expr; exp_symbol ex_sym; expression(double x):ex_sym(0) { char buffer[64]; sprintf(buffer,"%g", x); expr = buffer; } expression(const exp_symbol &sym, const string &l_expr, const exp_symbol &l_sym, const string &r_expr, const exp_symbol &r_sym):ex_sym(sym) { char op = sym.op; if( l_sym < sym ) expr = "( " + l_expr + " ) " + op + ' '; else expr = l_expr + ' ' + op + ' '; if( sym < r_sym ) expr += r_expr; else expr = expr + "( " + r_expr + " )"; } expression(const expression &exp):expr(exp.expr), ex_sym(exp.ex_sym){ } }; /* 从字符串中输入一个运算符 */ static int getsymbol(const char * &src_expr, exp_symbol &op_sym) { char op=0; int len=0; do { if(0 == sscanf(src_expr, "%c%n", &op, &len)) break; src_expr += len; } while( ' ' == op ); op_sym = exp_symbol(op); return (int)op_sym.op; } /** * @brief 后缀表达式转中缀表达式 * @note <表达式>=<常数>|<表达式><运算符><表达式> * @note 遇到常数,压栈;遇到运算符,从栈中弹出两个表达式,与运算符合成新的表达式,压栈;直到输入结束 */ int PostToMiddleExpr(const char * src_expr, string & dst_expr) { double x = 0.0; int len=0, bValid=1; exp_symbol op_sym(0); std::stack<expression> stExpr; while( bValid ) { bValid = 0; if( sscanf(src_expr, "%lf%n", &x, &len) > 0 ) /* 运算数,直接入栈 */ { src_expr += len; stExpr.push( expression(x) ); bValid = 1; } else if( getsymbol(src_expr, op_sym) > 0 ) /* 运算符,出栈两个表达式,组成新的表达式 */ { if(!stExpr.empty()) { const expression &expr2 = stExpr.top(); string r_expr = expr2.expr; exp_symbol r_sym = expr2.ex_sym; stExpr.pop(); if(!stExpr.empty()) { const expression &expr1 = stExpr.top(); string l_expr = expr1.expr; exp_symbol l_sym = expr1.ex_sym; stExpr.pop(); stExpr.push(expression(op_sym, l_expr,l_sym, r_expr, r_sym)); bValid = 1; } } } } /* 判断表达式栈并返回中缀表达式 */ if(stExpr.empty()) return -1; dst_expr = stExpr.top().expr; stExpr.pop(); if(!stExpr.empty()) { do{ stExpr.pop(); }while(!stExpr.empty()); return -1; } return 0; } /** * 后缀表达式转中缀表达式的试验程序~ */ int main( void ) { string dst_expr; const char *src_str = "19.3 23.4 - 3.5 * 1.7 + 1.4 / 3.4 *"; PostToMiddleExpr( src_str, dst_expr); cout << "dst_expr = "<< dst_expr << endl; return 0; }    

返回顶部
查看电脑版