最近做了一道关于表达式处理的算法题（CCF认证201903-2），说的是处理若干个中缀形式的表达式计算其真值的问题。这让我想起了大二做的一个Java Swing计算器，UI什么的很简单，但里面涉及了一个关于处理数学计算表达式的类。为了让这个Java课的实验成果看起来更丰富，我还添加了一些科学计算的功能 ，如求对数，开根号等。不过其中最核心的还是那个处理数学计算表达式的类 Helper，本文将介绍这个Helper类所涉及的原理，并给出相关代码。
人类最熟悉的一种表达式（1+2）*3、（3+4）*2+4等等都是中缀表示法。对于人们来说，也是最直观的一种求值方式，先算括号里的，然后算乘除，最后算加减，但是，计算机处理中缀表达式却并不方便，因为没有一种简单的数据结构可以方便从一个表达式中间抽出一部分算完结果，再放进去，然后继续后面的计算。
在考研复习的过程中，我了解到，一个算式表达式可以转化为一个二叉树的形式，如下图所示：
这颗二叉树对应的算式表达式为 A+B*(C-D)-E*F，也就是这个表达式的中缀形式。
但是由于计算机不方便处理这种便于人类理解的中缀形式，我们要将它进行转化。如果仔细观察，可以发现其实刚刚上面的中缀形式其实就是这个二叉树的中序遍历，而这个二叉树对应的前序遍历和后续遍历，就叫做这个表达式的波兰式和逆波兰式，它们在求值时会比中缀容易的多。
首先介绍一下如何将中缀表达式转化为逆波兰式，这里主要借助了栈的帮助，其实这个算法究其本质，就是利用了二叉树中序遍历转后序遍历的过程，需要调用栈来实现，只不过加上了表达式中运算优先级的限定，使得这个后序遍历（即逆波兰式）变得唯一
//输入：中缀表达式串 输出：逆波兰式串
string toPolish(string mid) {
string out; //输出串
stack<char> s; //用于存储操作符的栈
int l = mid.length();
for (int i = 0; i < l; i++) {
char t = mid[i];
if (t >= '0' && t <= '9') { //扫描到的mid[i]是操作数DATA
out += t; //直接加到输出串中
continue;
}
else { //是操作符
if (s.empty() || ((s.top() == '+' || s.top() == '-') && (t == '*' || t == '/'))) { //栈为空 或 扫描到的操作符优先级比栈顶操作符高
s.push(t); //入栈
continue;
}
else {
if (!s.empty()) { //出栈至输出串中
out += s.top();
s.pop();
}
out += t;
continue;
}
}
}
while (!s.empty()) { //扫描结束而栈中还有操作符
out += s.top(); //操作符出栈并加到输出串中
s.pop();
}
return out;
}
为了简化，这里直接使用了CCF算法题里我使用的转化函数，完整的计算器里面的处理过程在文末。
对于求逆波兰式的值的过程，只需要用一个栈实现：我们可以用一个栈S2来实现计算，扫描从左往右进行，如果扫描到操作数，则压进S2，如果扫描到操作符，则从S2弹出两个操作数进行相应的操作，并将结果压进S2(S2的个数出2个进1个),当扫描结束后，S2的栈顶就是表达式结果。对于这一过程的理解，手动模拟一次即可。下面仍然贴出我在算法题中使用的求真值的C++代码：
int getValue(string p) {
stack s2;
int l = p.length();
for (int i = 0; i < l; i++) {
char t = p[i];
if (t >= '0' && t <= '9') { //扫描到的p[i]是操作数DATA
int v = t - '0';
s2.push(v); //压进S2
}
else {//是操作符
int v1 = s2.top();
s2.pop();
int v2 = s2.top();
s2.pop();
int v = 0;
switch (t){ //从S2弹出两个操作数进行相应的操作
case '+':
v = v1 + v2;
break;
case '-':
v = v1 - v2;
break;
case '*':
v = v1 * v2;
break;
case '/':
v = v1 / v2;
break;
default:
break;
}
s2.push(v); //将结果压进S2
}
}
return s2.top(); //S2的栈顶就是表达式结果
}
到此，如何处理一个简单数学表达式的过程就已经展示完成了。显然这些代码的完成度不是很高，只能应付一下算法题，没有对于异常情况的处理，在真正的项目中是不能直接拿来用的。在开头提到的那个计算器，则充分考虑了各种异常情况，并且通过Java的异常处理throw出了计算过程中的各种异常，下面是处理表达式的Helper类代码
import java.util.Stack;
/**
* 处理标准的中缀表达式，式中不含科学计算
*/
public class Helper {
public static double st(String input) {
double r = 0;
if (input.length() != 0) {
try {
r = toPolishNotation(input);
} catch (NumberFormatException e) {
System.out.println("\n你输入的不是一个数字！");
} catch (IllegalArgumentException e) {
System.out.println("\n输入异常:" + e.getMessage());
} catch (Exception e) {
System.out.println("\n输入的表达式不合法！");
}
}
return r;
}
private static double toPolishNotation(String input)
throws IllegalArgumentException, NumberFormatException {
int len = input.length();
char c, tempChar;
Stack<Character> s1 = new Stack<Character>();
Stack<Double> s2 = new Stack<Double>();
Stack<Object> expression = new Stack<Object>();
double number;
int lastIndex = -1;
for (int i=len-1; i>=0; --i) {
c = input.charAt(i);
if (Character.isDigit(c)) {
lastIndex = readDoubleReverse(input, i);
number = Double.parseDouble(input.substring(lastIndex, i+1));
s2.push(number);
i = lastIndex;
if ((int) number == number)
expression.push((int) number);
else
expression.push(number);
} else if (isOperator(c)) {
while (!s1.isEmpty()
&& s1.peek() != ')'
&& priorityCompare(c, s1.peek()) < 0) {
expression.push(s1.peek());
s2.push(calc(s2.pop(), s2.pop(), s1.pop()));
}
s1.push(c);
} else if (c == ')') {
s1.push(c);
} else if (c == '(') {
while ((tempChar=s1.pop()) != ')') {
expression.push(tempChar);
s2.push(calc(s2.pop(), s2.pop(), tempChar));
if (s1.isEmpty()) {
throw new IllegalArgumentException(
"缺少右括号。");
}
}
} else if (c == ' ') {
// ignore
} else {
throw new IllegalArgumentException(
"错误字符 '" + c + "'");
}
}
while (!s1.isEmpty()) {
tempChar = s1.pop();
expression.push(tempChar);
s2.push(calc(s2.pop(), s2.pop(), tempChar));
}
while (!expression.isEmpty()) {
System.out.print(expression.pop() + " ");
}
double result = s2.pop();
if (!s2.isEmpty())
throw new IllegalArgumentException("输入的是一个错误的表达式。");
return result;
}
private static double calc(double num1, double num2, char op)
throws IllegalArgumentException {
switch (op) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
if (num2 == 0) throw new IllegalArgumentException("除数不能为零！");
return num1 / num2;
default:
return 0; // will never catch up here
}
}
private static int priorityCompare(char op1, char op2) {
switch (op1) {
case '+': case '-':
return (op2 == '*' || op2 == '/' ? -1 : 0);
case '*': case '/':
return (op2 == '+' || op2 == '-' ? 1 : 0);
}
return 1;
}
private static int readDoubleReverse(String input, int start)
throws IllegalArgumentException {
int dotIndex = -1;
char c;
for (int i=start; i>=0; --i) {
c = input.charAt(i);
if (c == '.') {
if (dotIndex != -1)
throw new IllegalArgumentException(
"数字中有多于一个的小数点。");
else
dotIndex = i;
} else if (!Character.isDigit(c)) {
return i + 1;
} else if (i == 0) {
return 0;
}
}
throw new IllegalArgumentException("这不是一个数字。");
}
private static boolean isOperator(char c) {
return (c=='+' || c=='-' || c=='*' || c=='/');
}
}
对于文章开头处提到的有些科学计算的功能，我还加入了一个用于预处理的类，它可以将包含科学表达式的原始式子递归简化成不包括科学表达式的式子，这个过程使得无论多么复杂的表达最终都可以被简化为一个简单式，并通过Helper求出其值，当然在递归简化的过程中，也需要调用Helper类来完成其中部分不含科学计算功能式子的简化，如(√(16*4))*log(10)³，就要先求出16*4和 (10)³ 的值，再继续简化，下面贴出这个预处理过程的代码
/**
* 用于将包含科学计算的式子,转换为不含科学计算的标准式子
*/
public class SCHelper {
public static boolean isSimpleWithoutBR(String s){
if(!isSimple(s))
return false;
if(s.contains("("))
return false;
if(s.contains(")"))
return false;
return true;
}
public static boolean isSimple(String s){
if(s.contains("^"))
return false;
if(s.contains("log"))
return false;
if(s.contains("²"))
return false;
if(s.contains("³"))
return false;
if(s.contains("√"))
return false;
return true;
}
public static boolean isNumber(String s){
if(s.contains("+"))
return false;
if(s.contains("-"))
return false;
if(s.contains("*"))
return false;
if(s.contains("/"))
return false;
if(s.contains("^"))
return false;
if(s.contains("log"))
return false;
if(s.contains("²"))
return false;
if(s.contains("³"))
return false;
if(s.contains("√"))
return false;
if(s.contains("("))
return false;
if(s.contains(")"))
return false;
return true;
}
private static String removeLog(String s){
if(!s.contains("log"))
return s;
int startIndex = s.indexOf("log");
int endIndex = s.indexOf(")",startIndex);
String old = s.substring(startIndex,endIndex+1); //原始式子里“log(x)”的字符串
String test = s.substring(startIndex+4,endIndex); //括号里的内容
double res = 0;
if(isNumber(test))
res = Math.log(Double.valueOf(test));
if(isSimpleWithoutBR(test))
res = Math.log(Helper.st(test));
String rep = Double.toString(res); //字符串形式的数字结果
s = s.replace(old,rep); //用数字替换原字符串
if(s.contains("log"))
s = removeLog(s); //递归删除所有log
return s;
}
private static String removeRadical(String s){
if(!s.contains("√"))
return s;
int startIndex = s.indexOf("√");
int endIndex = s.indexOf(")",startIndex);
String old = s.substring(startIndex,endIndex+1); //原始式子里“√(x)”的字符串
String test = s.substring(startIndex+2,endIndex);
double res = 0;
if(isNumber(test))
res = Math.sqrt(Double.valueOf(test));
if(isSimpleWithoutBR(test))
res = Math.sqrt(Helper.st(test));
String rep = Double.toString(res); //字符串形式的数字结果
s = s.replace(old,rep); //用数字替换原字符串
if(s.contains("√"))
s = removeRadical(s); //递归删除所有√
return s;
}
private static String removeQuad(String s){
if(!s.contains("²"))
return s;
int endIndex = s.indexOf("²");
int startIndex = s.lastIndexOf("(",endIndex);
String old = s.substring(startIndex,endIndex+1); //原始式子里“ (x)²”的字符串
String test = s.substring(startIndex+1,endIndex-1);
double res = 0;
if(isNumber(test))
res = Math.pow(Double.valueOf(test), 2);
if(isSimpleWithoutBR(test))
res = Math.pow(Helper.st(test),2);
String rep = Double.toString(res); //字符串形式的数字结果
s = s.replace(old,rep); //用数字替换原字符串
if(s.contains("²"))
s = removeQuad(s); //递归删除所有²
return s;
}
private static String removeCubic(String s){
if(!s.contains("³"))
return s;
int endIndex = s.indexOf("³");
int startIndex = s.lastIndexOf("(",endIndex);
String old = s.substring(startIndex,endIndex+1); //原始式子里“ (x)³”的字符串
String test = s.substring(startIndex+1,endIndex-1);
double res = 0;
if(isNumber(test))
res = Math.pow(Double.valueOf(test), 3);
if(isSimpleWithoutBR(test))
res = Math.pow(Helper.st(test),3);
String rep = Double.toString(res); //字符串形式的数字结果
s = s.replace(old,rep); //用数字替换原字符串
if(s.contains("³"))
s = removeCubic(s); //递归删除所有³
return s;
}
private static String removePower(String s){
if(!s.contains("^"))
return s;
//底数部分
int endIndex = s.indexOf("^");
int startIndex = s.lastIndexOf("(",endIndex);
//String old = s.substring(startIndex,endIndex+1); //原始式子里“ (x)^”的字符串
String test = s.substring(startIndex+1,endIndex-1);
//幂部分
int startIndex2= s.indexOf("^");
int endIndex2 = s.indexOf(")",startIndex2);
//String old2= s.substring(startIndex2,endIndex2+1); //原始式子里“^(x)”的字符串
String test2 = s.substring(startIndex2+2,endIndex2);
String old = s.substring(startIndex,endIndex2+1); //原始式子里“(x)^(y)”的字符串
double res;
double under = 0; //底数
double up = 0; //幂
if(isNumber(test))
under = Double.valueOf(test);
if(isSimpleWithoutBR(test))
under = Helper.st(test);
if(isNumber(test2))
up = Double.valueOf(test2);
if(isSimpleWithoutBR(test2))
up = Helper.st(test2);
res = Math.pow(under, up);
String rep = Double.toString(res); //字符串形式的数字结果
s = s.replace(old,rep); //用数字替换原字符串
if(s.contains("^"))
s = removePower(s); //递归删除所有^
return s;
}
public static double start(String str){
if(isSimple(str)) //如果为简单算式，直接交给Helper
return Helper.st(str);
if(str.contains("²")){
str = removeQuad(str);
}
if(str.contains("³")){
str = removeCubic(str);
}
if(str.contains("^")){
str = removePower(str);
}
if(str.contains("log")){
str = removeLog(str);
}
if(str.contains("√")) {
str = removeRadical(str);
}
if(isSimple(str)) //如果为简单算式，直接交给Helper
return Helper.st(str);
return -1;
}
}