最近在看《算法》这本书，正好看到一个计算表达式的问题，于是就打算写一下，也正好熟悉一下Java集合框架的使用，大致测试了一下，没啥问题。
import java.util.*;
/*
*
* 用来计算表达式
* for example: 1+2*3*(4+3*1)-3*1+2+3/1;
* (1+2*2-2*1*3*(1-1))*(1-2+3*(4+0));
* 注意点：
* 2.输入的表达书不能还有空格,括号必须匹配
* 基本思想：
* 1.建立操作数栈以及操作符栈
* 2.先去括号，每次遇到')'时，就退栈，直到遇到'('
* 3.然后处理括号中的表达式，先处理优先级高的，即*、/
* 4.处理好高优先级操作符之后，就处理+、-这种操作符
* 5.对以上的运算结果入栈，继续，处理完所有的(、)之后
* 6.然后再次求一般的表达式即可
*/ public class CalExpression { private Stack<Double > vals = new Stack<Double >();
private Stack<Character > ops = new Stack<Character >(); public static void main(String[] args) {
CalExpression obj = new CalExpression();
obj.input();
} public void input() {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
pushStack(in.next());
}
} public boolean check(char ch) {
if (ch == '(' || ch == ')' || ch == '+' || ch == '-'
|| ch == '*' || ch == '/') {
return true;
}
return false;
} public void pushStack(String str) {
//匹配非数字，将(、)、+、-、*、/作为分隔符
String[] strNum = str.split("[^0-9]"); Queue<Double > que = new LinkedList<Double >(); for (int i = 0; i < strNum.length; ++i) {
if (!strNum[i].equals("")) {
que.offer(Double.parseDouble(strNum[i]));
}
} boolean flag = false;
for (int i = 0; i < str.length(); ++i) {
if (check(str.charAt(i))) {
//匹配到右括号，需要计算括号中的内容
if (str.charAt(i) == ')') {
Deque<Character > ops_tmp = new LinkedList<Character >();
while (!ops.isEmpty() && ops.peek() != '(') {
ops_tmp.offerFirst(ops.pop());
}
//'('退栈
ops.pop();
calExpress(ops_tmp);
} else {
ops.push(str.charAt(i));
}
flag = false; } else if (!flag) {
vals.push(que.poll());
flag = true;
}
} double value = getValue(vals.iterator(), ops.iterator()); System.out.println(value);
vals.clear();
ops.clear(); } public void calExpress(Deque<Character > deq_ops) {
//操作数数目=操作符数目+1
int numCount = deq_ops.size() + 1; Deque<Double > deq_num = new LinkedList<Double >();
while (numCount > 0 && !vals.isEmpty()) {
deq_num.offerFirst(vals.pop());
numCount--;
} double value = getValue(deq_num.iterator(), deq_ops.iterator());
vals.push(value);
} public double getValue(Iterator it_num, Iterator it_ops) {
Deque<Double > vals = new LinkedList<Double >();
Deque<Character > ops = new LinkedList<Character >(); vals.offer((double)it_num.next());
while (it_num.hasNext()) {
char ch = (char)it_ops.next();
if (ch == '+' || ch == '-') {
vals.offer((double)it_num.next());
ops.offer(ch);
} else if (ch == '*' || ch == '/') {
double num = vals.pollLast();
if (ch == '*') {
vals.offer(num * (double)it_num.next());
} else {
vals.offer(num / (double)it_num.next());
}
}
} double value = vals.pollFirst();
while (!vals.isEmpty() && !ops.isEmpty()) {
if ((char)ops.pollFirst() == '+') {
value += vals.pollFirst();
} else {
value -= vals.pollFirst();
}
} return value;
} }