基于Java语言的表达式计算

一个表达式包含+、—、*、/、（）运算符，要计算表达式的值。此处运用栈，分别存储操作数和操作符，大体思路是利用双栈把中缀表达式转换成后缀表达式进行计算。

1.拆分数字与运算符
遇到运算符截断、存储、清空。
2.转后缀表达式
栈A存放后缀表达式，栈B存放运算符
记 B栈顶运算符为a1,当前运算符为a2（若a2为数字直接 a2->A ）
1）若 a1>a2，a1->A，a2->B
1）若 a1<a2，a2->B；
2）若 a1>=a2
1.若a1>a2，a1->A；（只要该条件满足则一直执行，使得优先级高的运算符放在A中）
2.将高级运算符都排除后，要判断a1=a2 ?（ 即是否为()相遇）
如果为左右括号的话就把做括号弹出，否则把a2->B。可以一直排除比它高级的运算法，但是只能抵消一个左括号
PS: a1>a2 表示 在此式中先算a1再算a2，a1与a2的关系在初始化中建立。
3.计算后缀表达式
从左往右扫描，遇到运算符则处理前两位数字

首先，将给定的字符串转为中缀表达式；使用List<String>保存表达式：程序代码如下

/**
* 将字符串转化为List
*
* @param str
* @return
*/
public ArrayList<String> getStringList(String str) {

ArrayList<String> result = new ArrayList<String>();

String num = "";

for (int i = 0; i < str.length(); i++) {

if (Character.isDigit(str.charAt(i)) || str.charAt(i) == ‘.‘) {

num = num + str.charAt(i);

} else {

if (num != "") {

result.add(num);

}

result.add(str.charAt(i) + "");

num = "";

}

}

if (num != "") {

result.add(num);
}

return result;

}

然后，将中缀表达式转变为后缀表达式，程序代码如下：

/**
* 将中缀表达式转化为后缀表达式
*
* @param inOrderList
* @return
*/
public ArrayList<String> getPostOrder(ArrayList<String> inOrderList) {

ArrayList<String> result = new ArrayList<String>();

Stack<String> stack = new Stack<String>();

stack.push("#");

for (int i = 0; i < inOrderList.size(); i++) {

if (Character.isDigit(inOrderList.get(i).charAt(0))) {

result.add(inOrderList.get(i));

} else {

switch (inOrderList.get(i).charAt(0)) {

case ‘(‘:

stack.push(inOrderList.get(i));

break;

case ‘)‘:

while (!stack.empty() && !stack.peek().equals("(")) {

result.add(stack.pop());
}

if (!stack.empty()) {
stack.pop();

}

break;

default:

while (!stack.empty() && !("#".equals(stack.peek()))
&& compare(stack.peek(), inOrderList.get(i))) {

result.add(stack.pop());

}

stack.push(inOrderList.get(i));

break;
}

}

}

while (!stack.empty() && !("#".equals(stack.peek()))) {

result.add(stack.pop());
}

return result;
}

其次，还得比较运算符的优先级，程序代码如下所示：

/**
* 比较运算符等级
*
* @param peek
* @param cur
* @return
*/
public static boolean compare(String peek, String cur) {

if ("*".equals(peek)
&& ("/".equals(cur) || "*".equals(cur) || "-".equals(cur) || "+"
.equals(cur))) {

return true;

} else if ("/".equals(peek)
&& ("/".equals(cur) || "*".equals(cur) || "-".equals(cur) || "+"
.equals(cur))) {

return true;

} else if ("+".equals(peek) && ("+".equals(cur) || "-".equals(cur))) {

return true;

} else if ("-".equals(peek) && ("+".equals(cur) || "-".equals(cur))) {

return true;

} else if ("#".equals(peek)) {

return true;
}

return false;

}

最后，计算表达式的值，程序代码如下：

/**
* 计算后缀表达式
*
* @param postOrder
* @return
*/
public Float calculate(ArrayList<String> postOrder) {

Stack<Float> stack = new Stack<Float>();
for (int i = 0; i < postOrder.size(); i++) {

if (Character.isDigit(postOrder.get(i).charAt(0))) {

stack.push(Float.valueOf(postOrder.get(i)));

} else {

Float back = (Float) stack.pop();

Float front = (Float) stack.pop();

float result = 0F;

switch (postOrder.get(i).charAt(0)) {

case ‘+‘:
result = front + back;

break;
case ‘-‘:
result = front - back;
break;
case ‘*‘:
result = front * back;
break;
case ‘/‘:
result = front / back;
break;
}

stack.push(result);
}
}

return stack.pop();

}

定义一个测试类，测试代码

public static void main(String[] args) {

EvaluateExpress exp = new EvaluateExpress();

String str = "24+（89-23*6）/3";

ArrayList<String> result = exp.getStringList(str);

System.out.print("中缀表达式：");

for (String s : result) {
System.out.print(s);
}

System.out.println("\n------------------");
ArrayList<String> postResult = exp.getPostOrder(result);
System.out.print("后缀表达式：");
for (String strs : postResult) {
System.out.print(strs);
}

System.out.println("\n-------------");
float calResult = exp.calculate(postResult);
System.out.println("计算结果为：" + calResult);

}