alightinthedark / expressionevaluator Goto Github PK

• 支持任意层嵌套括号的表达式求值，支持浮点数运算
• 完善的异常处理，能够判断表达式是否非法、操作数是否非法，并指出出错位置
• 表达式末尾可有=，可无=
• 支持英文字符大小写混用
• 负数可加括号，可不加括号
• 使用c++17标准和QT框架实现

• 二元运算符：+、-、x(*)、/、%、^
• 需要左操作数的一元运算符：！
• 需要右操作数的一元运算符: sin(可简写为s)、cos(c)、tan(t)、lg(g)、ln(n)、sqrt(q)、-(取反)
• 常量：pi, e

用户输入12（空格）34，可能他想输入的是12+34，不小心把中间的运算符丢掉了；也可能他想输入一个数字1234，不小心在12和34之间添加了一个空格。对于上述情况，本程序忽略空格，认为1234是一个完整的数字。

用户输入5sin（PI/2），可能他省略了5和sin之间的乘号，也可能他想计算的是5 - sin（PI/2），不小心丢掉了中间的运算符。对于上述情况，本程序认为5和sin之间缺失运算符，不支持所有的乘号省略。

常见的表达式求值算法有：

（1）基于中缀形式计算表达式，用到的数据结构为两个栈——操作数栈和操作符栈。

（2）基于后缀形式计算表达式，用到的数据结构为一个栈和一个队列。首先用栈将中缀表达式转换为后缀表达式，存放在队列中；接着对后缀表达式求值。

算法（1）更符合人的思维习惯，且有优秀的时间复杂度、空间复杂度，故采用算法（1）。

1. 表达式预处理：将表达式中的所有大写字母转换为小写字母；去除表达式中的所有空格；去掉表达式末尾的=；将自然常数e替换为”2.71828”，将圆周率PI替换为’’3.141593’’；把所有多字符的运算符替换为单字符，如sin替换为s；把所有表示乘法的x替换为*。

2. 自左向右逐个字符扫描字符串。

   • 如果该字符是数字（包括小数点），继续向右扫描，直到找到非数字的字符。将该字符与非数字字符之间的所有字符转换成一个浮点数，压入操作数栈中。从非数字字符开始继续扫描。

   • 该字符是需要左操作数的单目运算符：从操作数栈中弹出一个数字，与该运算符运算，结果压入操作数栈中。

   • 该字符是需要右操作数的单目运算符（包括负号）：压入运算符栈中。

   • 该字符是双目运算符：只要运算符栈不空，就进行如下循环：如运算符栈顶为单目运算符，弹出，与操作数栈中弹出的一个操作数运算，运算结果压入操作数栈；如运算符栈顶为双目运算符且其优先级大于等于该字符，从操作数栈中弹出两个操作数与栈顶运算符运算，结果压入操作数栈中。否则，退出循环。循环结束后，将该字符压入运算符栈。

   • 该字符是左括号：压入运算符栈。

   • 该字符是右括号：从运算符栈中弹出一个运算符，根据运算符是单目还是双目，从操作数栈中弹出一个或两个操作数，进行计算，结果压入操作数栈中。重复上述步骤，直到运算符栈中弹出左括号。

3. 扫描完整个字符串后，只要运算符栈不空，就进行如下循环：弹出栈顶运算符。如其为单目运算符，从操作数栈栈顶弹出一个操作数与其进行运算，将运算结果压入操作数栈。如其为双目运算符，从操作数栈中弹出两个操作数与其运算，运算结果压入操作数栈中。

4. 操作数栈中栈顶元素即为运算结果。

支持变量

支持大整数

支持科学计数法