Qt 第9课、计算器中缀转后缀算法

计算器核心算法：

1、将中缀表达式进行数字和运算符的分离
2、将中缀表达式转换成后缀表达式
3、通过后缀表达式计算最后的结果

---

二、计算器中缀转后缀算法

计算器中缀转后缀算法的意义在于把中缀表达式转换成后缀表达式，能够更好地计算

• 算法的基本思路
  1、如果是isNumber，直接进输出队列
  2、如果是isOperator，
  如果一个运算符优先级 <= 前一个运算符优先级，则这个前面那个运算符进输出队列
  其余的全部进栈
  3、如果是左括号，进栈
  4、如果是右括号，直到栈顶为左括号才不用把栈里的进输出队列，
  把栈顶元素pop()
  5、其余的报错
  如果栈里面不为空，直接全部进队列

bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
{bool ret = match(exp);output.clear();QStack<QString> stack;while(ret && !exp.isEmpty()){QString str = exp.dequeue();if(isNumber(str)){output.enqueue(str);}else if(isOperator(str)){while(!stack.isEmpty() && priority(str) <= priority(stack.top())){output.enqueue(stack.pop());}stack.push(str);}else if(isLeft(str)){stack.push(str);}else if(isRight(str)){while(!stack.isEmpty() && !isLeft(stack.top())){output.enqueue(stack.pop());}stack.pop();}else{ret = false;}}while(!stack.isEmpty()){output.enqueue(stack.pop());}if(!ret){output.clear();}return ret;
}

4、计算器后缀表达式计算算法

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 == "/"){double delta = 0.0000000001;if(rp >= -delta && rp <= delta){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 str = exp.dequeue();if(isNumber(str)){stack.push(str);}else if(isOperator(str)){QString rp = !stack.isEmpty() ? stack.pop() : "";QString lp = !stack.isEmpty() ? stack.pop() : "";QString result = calculate(lp, str, rp);if(result != "Error"){stack.push(result);}else{break;}}}if(exp.isEmpty() && stack.size() == 1 && isNumber(stack.top())){ret = stack.pop();}return ret;
}

5、通过一个函数包含所有计算器的核心算法

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;
}

计算器算法实现的源代码：

QCalculatorDec.h

#ifndef QCALCULATORDEC_H
#define QCALCULATORDEC_H
#include <QQueue>
#include <QString>
#include <QStack>#include "ICalculator.h"
class QCalculatorDec
{
protected:QString m_exp;QString m_result;bool isDigitOrDot(QChar c);bool isSign(QChar c);bool isSymbol(QChar c);bool isOperator(QString s);bool isLeft(QString s);bool isRight(QString s);bool isNumber(QString s);int priority(QString s);QQueue<QString> split(const QString& exp);bool match(QQueue<QString>& exp);bool transform(QQueue<QString>& exp, QQueue<QString>& output);QString calculate(QString l, QString op, QString r);QString calculate(QQueue<QString>& exp);
public:QCalculatorDec();bool expression(const QString& exp);QString expression();QString result();~QCalculatorDec();
};#endif // QCALCULATORDEC_H

QCalculatorDec.cpp

#include "QCalculatorDec.h"
#include <QDebug>
QCalculatorDec::QCalculatorDec()
{m_exp = "";m_result = "";
}bool QCalculatorDec::isDigitOrDot(QChar c)
{return ((c >= '0')&&(c <= '9'))||(c == '.');
}bool QCalculatorDec::isSign(QChar c)
{return (c == '+')||(c == '-');
}bool QCalculatorDec::isSymbol(QChar c)
{return isOperator(c)||(c == '(')||(c == ')');
}bool QCalculatorDec::isOperator(QString s)
{return (s == "+")||(s == "-")||(s == "*")||(s == "/");
}bool QCalculatorDec::isLeft(QString s)
{return (s == "(");
}bool QCalculatorDec::isRight(QString s)
{return (s == ")");
}bool QCalculatorDec::isNumber(QString s)
{bool ret = false;s.toDouble(&ret);return ret;
}int QCalculatorDec::priority(QString s)
{int ret = 0;if(s == "+"||s == "-"){ret = 1;}else if(s == "*"||s == "/"){ret = 2;}return ret;
}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 == "" || isLeft(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;QStack<QString> stack;for(int i = 0; i < exp.length(); i++){if(isLeft(exp[i])){stack.push(exp[i]);}else if(isRight(exp[i])){if(isLeft(stack.top())){stack.pop();}else{ret = false;}}}if(!stack.isEmpty()){ret = false;}return ret;
}bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
{bool ret = match(exp);output.clear();QStack<QString> stack;while(ret && !exp.isEmpty()){QString str = exp.dequeue();if(isNumber(str)){output.enqueue(str);}else if(isOperator(str)){while(!stack.isEmpty() && priority(str) <= priority(stack.top())){output.enqueue(stack.pop());}stack.push(str);}else if(isLeft(str)){stack.push(str);}else if(isRight(str)){while(!stack.isEmpty() && !isLeft(stack.top())){output.enqueue(stack.pop());}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 == "/"){double delta = 0.0000000001;if(rp >= -delta && rp <= delta){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 str = exp.dequeue();if(isNumber(str)){stack.push(str);}else if(isOperator(str)){QString rp = !stack.isEmpty() ? stack.pop() : "";QString lp = !stack.isEmpty() ? stack.pop() : "";QString result = calculate(lp, str, rp);if(result != "Error"){stack.push(result);}else{break;}}}if(exp.isEmpty() && stack.size() == 1 && isNumber(stack.top())){ret = stack.pop();}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::expression()
{return  m_exp;
}QString QCalculatorDec::result()
{return m_result;
}QCalculatorDec::~QCalculatorDec()
{}