中缀表达式一般是先转换为后缀表达式，然后再计算的，其实我们可以边转换边计算。
/*Infix.java
使用两个栈直接求解中缀表达式，一个栈保存运算符S，一个栈保存操作数D。
例子：
a+b*c
D:a,b S:+
D:a,b,c S:+,*
D:a,bc S:+ <-- 每次取一个运算符，弹两个操作数
D:a+bc S:
a*b/c+d
D: a,b S:*
D: a*b S:/ <-- 清空优先级大于等于除号的运算符
D:a*b/c S:+
D:a*b/c+d S:
a^b^c
D:a,b S:^
D:a,b,c S:^,^ <-- 清空栈优先级大于等于幂号扫描优先级的运算符
D:a,b^c S:^
D:a^b^c S:
a*(b+c)
D:a S:*(
D:a,b S:*(+
D:a,b,c S:*(+)
D:a,b+c S:* <-- 清空操作符直到(
D:a*(b+c) S:
这几种情形，通过赋予运算符适当的优先级，可统一为：
清空栈优先级大于等于扫描优先级的运算符 (R0)
这里只是为了说明栈的应用，因此简单假设操作数是一位数字，并且没有空格，
如果扩展成BigDecimal应该不困难。
中缀表达式的计算规则，从左到右扫描一遍，在扫描过程中：
R1 如果遇到数字，则压入操作数栈D；
R2 如果遇到操作符，则根据R0弹出S中的操作符；
R3 每弹出一个操作符，就弹出D中两个操作数，并把结果压入D。
扫描结束时，可能S不为空，按规则R3。最终D中仅有的一个是结果，S 应该为空。
author: ludi 2014.04
*/
import java.util.Stack;
public class Infix
{
public static int eval(int a, int b, char op)
{
int ret = 0;
switch(op){
case ‘+‘: ret = a + b; break;
case ‘-‘: ret = a - b; break;
case ‘*‘: ret = a * b; break;
case ‘/‘: ret = a / b; break;
case ‘%‘: ret = a % b; break;
case ‘^‘: {
ret = 1;
while(b-- > 0){
ret *= a;
}
}break;
default: System.out.println("error op " + op); break;
}
return ret;
}
public static int evaluate(String infix)
{
Stack<Integer> d = new Stack<Integer>();
Stack<Symbol> s = new Stack<Symbol>();
int i, a, b;
char ch;
Symbol op, op2;
for(i = 0; i < infix.length(); ++i){
ch = infix.charAt(i);
if (Character.isDigit(ch)){
d.push(ch - ‘0‘);
}else {
op = new Symbol(ch);
while(!s.empty() && (s.peek().compareTo(op) >= 0)){
op2 = s.pop();
b = d.pop();
a = d.pop();
d.push(eval(a, b,op2.op));
}
if(ch == ‘)‘){
s.pop(); /*弹出‘(‘*/
}else s.push(op);
}
}
while(!s.empty()){
op2 = s.pop();
b = d.pop();
a = d.pop();
d.push(eval(a, b, op2.op));
}
System.out.printf("%s = %d d.size %d s.size %d%n", infix, d.peek(), d.size(), s.size());
return d.pop();
}
public static void main(String[] arg)
{
evaluate("1+2*3");
evaluate("2*(3+4)");
evaluate("2*3/2+1");
evaluate("2^3^2");
evaluate("(2^3)^2");
evaluate("(2^3)^2+2^3^2+2*3/2+1+2*(3+4)");
evaluate("2^(2*(3+4))");
}
}
class Symbol implements Comparable<Symbol>
{
char op;
int inputPrec; /*正在被扫描的操作符的优先级*/
int stackPrec; /*栈优先级：值越小停留在栈中时间越长*/
public Symbol (char ch){
op = ch;
switch(op){
case ‘+‘:
case ‘-‘:inputPrec = stackPrec = 1;
break;
case ‘*‘:
case ‘%‘:
case ‘/‘: inputPrec = 2;
stackPrec = 2;
break;
case ‘^‘:
inputPrec = 4;
stackPrec = 3; /*右结合的操作符扫描大于栈优先级*/
break;
case ‘(‘:
inputPrec = 5;
stackPrec = -1; /*最高的扫描优先级，最低的栈优先级*/
break;
case ‘)‘:
inputPrec = 0;
stackPrec = 0;
break;
}
}
public int compareTo(Symbol item)
{
int result;
if (stackPrec < item.inputPrec)
result = -1;
else if (stackPrec == item.inputPrec)
result = 0;
else
result = 1;
return result;
}
public char getOp()
{ return op; }
}
/*
ludi@msys ~/java
$ javac -encoding UTF-8 Infix.java && java Infix
1+2*3 = 7 d.size 1 s.size 0
2*(3+4) = 14 d.size 1 s.size 0
2*3/2+1 = 4 d.size 1 s.size 0
2^3^2 = 512 d.size 1 s.size 0
(2^3)^2 = 64 d.size 1 s.size 0
(2^3)^2+2^3^2+2*3/2+1+2*(3+4) = 594 d.size 1 s.size 0
2^(2*(3+4)) = 16384 d.size 1 s.size 0
ludi@msys ~/java
*/
这里面为了简明起见，没有做错误处理。
很好奇编译器是怎么计算常量表达式的，不知道是不是这样子呢。
附：
一些与栈有关的有意思的话题：
[1] 神奇的卡塔兰数Catalan http://blog.csdn.net/nupt123456789/article/details/22735113