Qt学习12 计算器核心解析算法 (上)

问题

计算机如何读懂四则运算表达式？ 9.3 + ( 3 - -0.11 ) * 5

后缀表达式

• 人类习惯的数学表达式叫做中缀表达式

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

• 实例：

  5 + 3 => 5 3 +

  1 + 2 * 3 => 1 2 3 * +

  9 + ( 3 - 1 ) * 5 => 9 3 1 - 5 * +

中缀 or 后缀

• 中缀表达式符合人类的阅读和思维习惯
• 后缀表达式符合计算机的运行方式
  • 消除了中缀表达式中的括号
  • 同时保留中缀表达式中的运算优先级

计算器核心算法

• 解决方案

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

  2.将中缀表达式转换为后缀表达式

  3.通过后缀表达式计算最终结果

分离算法分析

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

  • 数字和小数点 [0 - 9 或 .
  • 符号位 [ + 或 - ]
  • 运算符 [ +，-，*，/ ]
  • 括号 [ ( 或 ) ]

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

  • 定义累计变量num

  • 当前字符 exp[i] 为数字或小数点时：

    • 累计：num += exp[i]

  • 当前字符为 exp[i] 为符号时：

    • num为运算数，分离并保存

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

    • 若 exp[i] 为运算符：分离并保存

• 伪代码

for (int i = 0; i < exp.length(); i++) {
    if (exp[i] 为数字或小数点) {
        累计: num += exp[i]；
    }
    else if (exp[i] 为符号) {
        if (num != "") {
            分离并保存运算数: num
        }
        if (exp[i] 为正好或负号) {
            符号位累计: num += exp[i];
        }
        else {
            分离并保存运算符: exp[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 难点：

  • 如何区分正负号与加号和减号？

    • +和-在表达式的第一个位置
    • 括号后的 + 和 -
    • 运算符后的 + 和 -

  • +9 + (-3 - -1) * -5

分离算法实现如下

/* QCalculatorDec.h */
#include <QString>
#include <QQueue>

class QCalculatorDec
{
protected:
    bool isDigitOrDot(QChar c);
    bool isSymbol(QChar c);
    bool isSign(QChar c);
    bool isNumber(QString s);
    bool isOperator(QString s);
    bool isLeft(QString s);
    bool isRight(QString s);
    int priority(QString s);
    QQueue<QString> split(const QString& exp);
public:
    QCalculatorDec();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* QCalculatorDec.cpp */
#include "QCalculatorDec.h"
#include <QDebug>

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

QQueue<QString> QCalculatorDec::split(const QString &exp) {
    QString num = "";
    QString pre = "";
    QQueue<QString> ret;
    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 != "") {
                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::isOperator(QString s) {
    return (s == '+') || (s == '-') || (s == '*') || (s == '/');
}

QCalculatorDec::QCalculatorDec() {
    QQueue<QString> r = split("-9.3 + ( 3 - 0.11 ) * 5");
    for (int i = 0; i < r.length(); i++) {
        qDebug() << r[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

小结

• QString中的每个字符为QChar
• Qt中提供了开发中不可或缺的数据结构类
• 四则运算表达式的计算分为三个步骤
  • 数字和符号分离
  • 中缀表达式转后缀表达式
  • 根据后缀表达式计算结果