学步园

中缀表达式 --> 后缀表达式，转换过程中同时计算

操作符堆栈（OperatorHeap）：

import java.util.Arrays;

public class OperatorHeap 
...{
    private char[] data;
    private int size;
    
    public OperatorHeap()
    ...{
        this(10);
    }
    public OperatorHeap(int size)
    ...{
        data = new char[size];
        initHeap();
    }
    
    public void initHeap()
    ...{
        data[size++] = '#';
    }
    
    //栈顶
    public char top()
    ...{
        return data[size-1];
    }
    
    //入栈
    public void push(char c)
    ...{
        ensureCapacity(size + 1);
        data[size++] = c;
    }
    
    //出栈
    public char pop()
    ...{
        return data[--size];
    }
    
    //扩展容量
    public void ensureCapacity(int minSize) 
    ...{
        int oldCapacity = data.length;
        if (minSize > oldCapacity) ...{
            int newCapacity = (oldCapacity * 3 / 2 + 1) > minSize ? 
                    oldCapacity * 3 / 2 + 1 : minSize;
            data = (char[]) Arrays.copyOf(data, newCapacity);
        }
    }
}

 操作数堆栈（NumHeap）：

import java.util.Arrays;

public class NumHeap 
...{
    private double[] data;
    private int size;
    
    public NumHeap()
    ...{
        this(10);
    }
    public NumHeap(int size)
    ...{
        data = new double[size];
    }
    
    //栈顶
    public double top()
    ...{
        return data[size-1];
    }
    
    //入栈
    public void push(double c)
    ...{
        ensureCapacity(size + 1);
        data[size++] = c;
    }
    
    //出栈
    public double pop()
    ...{
        return data[--size];
    }
    
    //扩展容量
    public void ensureCapacity(int minSize) 
    ...{
        int oldCapacity = data.length;
        if (minSize > oldCapacity) ...{
            int newCapacity = (oldCapacity * 3 / 2 + 1) > minSize ? 
                    oldCapacity * 3 / 2 + 1 : minSize;
            data = (double[]) Arrays.copyOf(data, newCapacity);
        }
    }
}

Eval类，提供了一个静态的eval方法，用于计算表达式值：

/** *//**
 * 计算表达式的值，如 3+(2+9*7)/5
 * @author Liw
 * @time 2007-6
 */

public class Eval 
...{    
    public static double eval(String str)
    ...{
        str = str + "#"; //设置"#"优先级最低，保证opHeap里的运算符能够全部退栈
        String[] words = str.split("(?<!^-?|[+/*()-]-)((?<=[+/*()-])|(?=[+/*()-]))"); //分割表达式
        OperatorHeap opHeap = new OperatorHeap();  //操作符堆栈
        NumHeap numHeap = new NumHeap();  //操作数堆栈
        
        for (int i = 0; i < words.length; i++) ...{
            if (words[i].matches("-?//d+|-?//d+//.//d+")) ...{  //操作数
                numHeap.push(Double.parseDouble(words[i]));  //操作数入栈
            }
            else ...{  //操作符
                char op_top = opHeap.top(), op_cur = words[i].toCharArray()[0]; //栈顶操作符&当前读取的操作符
                while (compare(op_top, op_cur)) ...{  //若当前操作符op_cur优先级低于栈顶，退栈，直到op_cur优先级大于栈顶
                    if ((op_top == '(' && op_cur == ')') || (op_top == '#' && op_cur == '#')) ...{
                        opHeap.pop();  //弹出"(" or "#"
                        break;
                    }
                    else ...{  //弹出一运算符
                        double a = numHeap.pop(), b = numHeap.pop();  //弹出两个数字用于计算
                        numHeap.push(eval2(b, a, opHeap.pop()));  //弹出一运算符，计算两个数的值，结果入栈
                        op_top = opHeap.top();  //新的栈顶
                    }
                }
                if (op_cur != ')') ...{
                    opHeap.push(op_cur);  //操作符op_cur入栈
                }
            }
        }
        
        return numHeap.top();
    }
    
    private static double eval2(double a,