第十二课、计算器的核心解析算法（上）------------------狄泰软件学院

一、后缀表达式

1、人类习惯的数学表达式叫中缀表达式

2、另外，还有一种将运算符放在数字后面的表达式叫后缀表达式

2、中缀 or 后缀

（1）、中缀表达式符合人类的阅读和思维习惯

（2）、后缀表达式符合计算机的运算方式

A、消除了中缀表达式中的括号

B、同时保留了中缀表达式中的优先级

二、计算器的核心算法

1、解决方案

（1）、将中缀表达式进行数字和运算符的分离

（2）、将中缀表达式转化为后缀表达式

（3）、通过后缀表达式计算最终结果

三、分离算法的分析

1、所要计算的中缀表达式中包含

2、思想：以符号作为标志，对表达式中的字符逐个访问

（1）、定义累计变量num

（2）、当前字符exp[i]为数字或者小数点时：完事后保存pre

A、累计 num += exp[i]

（3）、当前字符exp[i]为符号时：完事后保存pre

A、num为运算数，分离并保存，并将num清空

B、若exp[i]为正负号：累计符号位 + 和 -：num += exp[i]

C、若exp[i]为运算符，分离并保存

（4）、将最后一个num保存

3、难点：如何区分正负号与加号和减号

（1）、+和- 在表达式的第一个位置

（2）、左括号后的+和-

（3）、运算符后的+和-

//CalculatorDec.h

#ifndef CALCULATORDEC_H
#define CALCULATORDEC_H

#include<QQueue>
#include <QString>
class CalculatorDec
{
    bool isDigitOrDot(QChar c);//数字和.
    bool isSymbol(QChar c);//字符
    bool isSign(QChar c);//符合+-
    bool isOperator(QString s);//参数为Qstring 的原因是后面要将pre作为参数传入

    QQueue<QString> split(const QString& exp);//将分离后的结果保存到队列中
public:
    CalculatorDec();
    ~CalculatorDec();
};

#endif // CALCULATORDEC_H

//CalculatorDec.cpp

#include "CalculatorDec.h"
#include <QDebug>

CalculatorDec::CalculatorDec()
{
    QQueue<QString> r = split("+9--8+(+4)-5");

    for(int i=0; i<r.length(); i++)
    {
        qDebug() << r[i];
    }

}

bool CalculatorDec::isDigitOrDot(QChar c)
{
    return ( ('0' <= c) && (c <= '9') ) || (c == '.');
}

bool CalculatorDec::isSymbol(QChar c)
{
    return isOperator(c) || (c == '(') || (c == ')');
}

bool CalculatorDec::isSign(QChar c)
{
    return (c == '+') || (c == '-');
}

bool CalculatorDec::isOperator(QString s)
{
    return (s == "+") || (s == "-") || (s == "*") || (s == "/");
}

QQueue<QString> CalculatorDec::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)))//判断是不是符号'+'和'-',注意传入的pre是字符串
            {
                num += exp[i];
            }
            else
            {
                ret.enqueue(exp[i]);
            }
            pre = exp[i];

        }
    }

    if(! num.isEmpty())
    {
        ret.enqueue(num);//最后一个操作数入列
    }
    return ret;
}

CalculatorDec::~CalculatorDec()
{
    
}

//main.cpp

#include <QtGui/QApplication>
#include "CalculatorDec.h"

int main(int argc, char *argv[])
{
   // QApplication a(argc, argv);
    CalculatorDec w;

    return 0;
}

四、小结

（1）、Qstring中的每一个字符为Qchar（2字节）

（2）、Qt中提供了开发中不可或缺的数据结构类

（3）、四则运算表达式的计算分三个步骤

A、数字和符号分离（本节课只实现了分离）

B、中缀表达式转为后缀表达式

C、根据后缀表达式计算结果