计算器字符串转换问题
计算器字符串转换问题
一. 中缀表达式和后缀表达式
-
中缀表达式(人类可以看懂的四则运算表达式,运算符在运算元素中间)
( 1 + 2 ) ∗ 3 − − 6 (1+2)*3--6 (1+2)∗3−−6 -
计算机计算的逻辑是,一个双目运算符对应一个运算指令,参与运算的是两个数字,所以一般表示成 如下格式
(1+2)==》 1 2 +
3*3 ==》 3 3 *
9- -6 ==》 9 -6 -
二. 解决方法
-
将中缀表达式进行数字和运算符的分离
包含的元素有: 数字和小数点:0~9和. 符号位:+或- 运算符:+ - * / 括号:( )
-
将中缀表达式转换为后缀表达式
难点: 分离数字和运算符 正负号和加减运算符的区分 四则运算表达式括号必须匹配 根据运算符优先级进行转换
-
通过后缀表达式计算最终结果
三. 算法实现
-
参考代码
#include "QCalculatorDec.h" QCalculatorDec::QCalculatorDec() { m_exp = ""; m_result = ""; } QCalculatorDec::~QCalculatorDec() { } bool QCalculatorDec::isDigitOrDot(QChar c) { return (('0' <= c) && (c <= '9')) || (c == '.'); } bool QCalculatorDec::isSymbol(QChar c) { return isOperator(c) || (c == '(') || (c == ')'); } bool QCalculatorDec::isSign(QChar c) { return (c == '+') || (c == '-'); } bool QCalculatorDec::isNumber(QString s) { bool ret = false; s.toDouble(&ret); return ret; } bool QCalculatorDec::isOperator(QString s) { return (s == "+") || (s == "-") || (s == "*") || (s == "/"); } bool QCalculatorDec::isLeft(QString s) { return (s == "("); } bool QCalculatorDec::isRight(QString s) { return (s == ")"); } int QCalculatorDec::priority(QString s) { int ret = 0; if( (s == "+") || (s == "-") ) { ret = 1; } if( (s == "*") || (s == "/") ) { ret = 2; } return ret; } bool QCalculatorDec::expression(const QString& exp) { bool ret = false; QQueue<QString> spExp = split(exp); QQueue<QString> postExp; m_exp = exp; if( transform(spExp, postExp) ) { m_result = calculate(postExp); ret = (m_result != "Error"); } else { m_result = "Error"; } return ret; } QString QCalculatorDec::result() { return m_result; } QQueue<QString> QCalculatorDec::split(const QString& exp) { QQueue<QString> ret; QString num = ""; QString pre = ""; for(int i=0; i<exp.length(); i++) { if( isDigitOrDot(exp[i]) ) { num += exp[i]; pre = exp[i]; } else if( isSymbol(exp[i]) ) { if( !num.isEmpty() ) { ret.enqueue(num); num.clear(); } if( isSign(exp[i]) && ((pre == "") || (pre == "(") || isOperator(pre)) ) { num += exp[i]; } else { ret.enqueue(exp[i]); } pre = exp[i]; } } if( !num.isEmpty() ) { ret.enqueue(num); } return ret; } bool QCalculatorDec::match(QQueue<QString>& exp) { bool ret = true; int len = exp.length(); QStack<QString> stack; for(int i=0; i<len; i++) { if( isLeft(exp[i]) ) { stack.push(exp[i]); } else if( isRight(exp[i]) ) { if( !stack.isEmpty() && isLeft(stack.top()) ) { stack.pop(); } else { ret = false; break; } } } return ret && stack.isEmpty(); } bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output) { bool ret = match(exp); QStack<QString> stack; output.clear(); while( ret && !exp.isEmpty() ) { QString e = exp.dequeue(); if( isNumber(e) ) { output.enqueue(e); } else if( isOperator(e) ) { while( !stack.isEmpty() && (priority(e) <= priority(stack.top())) ) { output.enqueue(stack.pop()); } stack.push(e); } else if( isLeft(e) ) { stack.push(e); } else if( isRight(e) ) { while( !stack.isEmpty() && !isLeft(stack.top()) ) { output.enqueue(stack.pop()); } if( !stack.isEmpty() ) { stack.pop(); } } else { ret = false; } } while( !stack.isEmpty() ) { output.enqueue(stack.pop()); } if( !ret ) { output.clear(); } return ret; } QString QCalculatorDec::calculate(QString l, QString op, QString r) { QString ret = "Error"; if( isNumber(l) && isNumber(r) ) { double lp = l.toDouble(); double rp = r.toDouble(); if( op == "+" ) { ret.sprintf("%f", lp + rp); } else if( op == "-" ) { ret.sprintf("%f", lp - rp); } else if( op == "*" ) { ret.sprintf("%f", lp * rp); } else if( op == "/" ) { const double P = 0.000000000000001; if( (-P < rp) && (rp < P) ) { ret = "Error"; } else { ret.sprintf("%f", lp / rp); } } else { ret = "Error"; } } return ret; } QString QCalculatorDec::calculate(QQueue<QString>& exp) { QString ret = "Error"; QStack<QString> stack; while( !exp.isEmpty() ) { QString e = exp.dequeue(); if( isNumber(e) ) { stack.push(e); } else if( isOperator(e) ) { QString rp = !stack.isEmpty() ? stack.pop() : ""; //从栈中弹出右操作数 QString lp = !stack.isEmpty() ? stack.pop() : ""; //从栈中弹出左操作数 QString result = calculate(lp, e, rp); //根据符号进行运算 if( result != "Error" ) { stack.push(result); //将计算结果压入栈中 } else { break; } } else { break; } } //后缀表达式为空,栈中最后一个元素为一个数 if( exp.isEmpty() && (stack.size() == 1) && isNumber(stack.top()) ) { ret = stack.pop(); //计算结果 弹栈 } return ret; }