Qt学习13 计算器核心解析算法 (中)

中缀转后缀

• 中缀表达式转后缀表达式的过程类似编译过程

  • 四则运算表达式中的括号必须匹配
  • 根据运算符优先级进行转换
  • 转换后的表达式中没有括号
  • 转换后可以顺序的计算出最终结果

• 转换过程：

  • 当前元素e为数字：输出

  • 当前元素e为运算符：

    1.与栈顶运算符进行优先级比较

    2.小于等于：将栈顶元素输出，转1

    3.大于：将当前元素e入栈

  • 当前元素e为左括号：入栈

  • 当前元素e为右括号：

    1.弹出栈顶元素并输出，直至栈顶元素为左括号

    2.将栈顶的左括号从栈中弹出

• 伪代码

while (!exp.isEmpty()) {
    QString e = exp.dequeue();
    if (isNumber(e)) {
        输出: e;
    }
    else if (isOperator(e)) {
        while (priority(e) <= priority(stack.top())) {
            输出栈顶元素, stack.pop();
        }
        stack.push(e);
    }
    else if (isLeft(e)) {
        stack.push(e);
    }
    else if (isRight(e)) {
        while (!isLeft(stack.top())) {
            输出栈顶元素, stack.pop();
        }
        从栈中弹出左括号: stack.pop();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 关键点：转换过程中左右括号是重要标志

  如何确保表达式中的括号能够左右匹配？

括号匹配算法

• 合法的四则运算表达式中
  • 括号匹配成对出现
  • 左括号必然咸鱼右括号出现

for (int i = 0; i < len; i++) {
    if (exp[i] 为左括号) {
        exp[i] 入栈;
    }
    else if (exp[i] 为右括号) {
        if (栈顶元素为左括号) {
            将栈顶元素弹出;
        }
        else
            匹配错误;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

括号匹配代码

bool QCalculatorDec::match(QQueue<QString> &exp) {
    bool ret = true;
    QStack<QString> s;
    for (int i = 0; i < exp.length(); i++) {
        if (isLeft(exp[i])) {
            s.push(exp[i]);
        }
        else if (isRight(exp[i])) {
            if (!s.isEmpty() && isLeft(s.top())) {
                s.pop();
            }
            else {
                ret = false;
                break;
            }
        }
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

中缀转后缀代码

bool QCalculatorDec::transfor(QQueue<QString> &exp, QQueue<QString> &output) {
    bool ret = match(exp);
    QStack<QString> s;
    output.clear();
    while (!exp.isEmpty()) {
        QString e = exp.dequeue();
        if (isNumber(e)) {
            output.enqueue(e);
        }
        else if (isOperator(e)) {
            while (!s.isEmpty() && priority(e) <= priority(s.top())) {
                output.enqueue(s.pop());
            }
            s.push(e);
        }
        else if (isLeft(e)) {
            s.push(e);
        }
        else if (isRight(e)) {
            while (!s.isEmpty() && !isLeft(s.top())) {
                output.enqueue(s.pop());
            }
            if (!s.isEmpty()) {
                s.pop();
            }
        } else {
            ret = false;
        }
    }
    while (!s.isEmpty()) {
        output.enqueue(s.pop());
    }
    if (!ret) {
        output.clear();
    }
    return ret;
}
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

小结

• 后缀表达式是程序计算复杂表达式的基础
• 中缀到后缀的转换是基于栈数据结构的
• 转换过程能够发现表达式中的语法错误