12_计算器核心解析算法(上)

声明：此文章仅是本人在学习狄泰QT实验分析课程所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4

1. 问题：计算机如何读懂四则运算表达式？

后缀表达式

2. 中缀表达式VS后缀表达式

人类习惯的数学表达式为中缀表达式，另外还有一种将运算符放在数字后面的后缀表达式。

中缀表达式转换为后缀表达式

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

3. 计算器核心算法

思路：

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

4. 分离算法分析

• 中缀表达式中包含了：数字和小数点[0-9 or .]、符号位[+ or -]、运算符[+, -, * , /]、括号[( or )]

• 分离算法思想：以符号作为标志对表达式中的字符逐个访问
  (1) 定义累计变量num
  (2) 当前字符exp[i]为数字或小数点时：
  累计：num += exp[i]
  (3) 当前字符exp[i]为符号时：
  num为运算数，分离并保存；
  若exp[i]为正负号： 累计符号位+和- num += exp[i]
exp[i]为运算符：分离并保存

• 分离算法伪代码：

  

• 分离算法难点：如何正确区分正负号和加减号？
  以下三种情况为正负号：
  1）前一个字符为空
  2）前一个字符为左括号
  3）前一个字符为操作符

编程说明：计算器中表达式分离算法实现

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

5. 小结

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