声明：此文章仅是本人在学习狄泰QT实验分析课程所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
1. 问题：计算机如何读懂四则运算表达式？
后缀表达式
2. 中缀表达式VS后缀表达式
人类习惯的数学表达式为中缀表达式，另外还有一种将运算符放在数字后面的后缀表达式。
中缀表达式转换为后缀表达式
- 中缀表达式符合人类的阅读和思维习惯
- 后缀表达式符合计算机的运行方式
消除了中缀表达式中的括号
同时保留了中缀表达式中的运算优先级
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) 根据后缀表达式计算结果
