首页 > 代码库 > java stack实现的中缀简单四则运算表达式计算

java stack实现的中缀简单四则运算表达式计算

public abstract class Stack<T> {    public abstract boolean isEmpty();    public abstract boolean isFull();    public abstract T top();    public abstract boolean push(T x);    public abstract T pop();    public abstract void clear();}
public class SeqStack<T> extends Stack<T> {    private Object[] elementData;    private int maxTop;    private int top;    public SeqStack(int size) {        this.maxTop = size - 1;        elementData = new Object[size];        top = -1;    }    @Override    public boolean isEmpty() {        return top == -1;    }    @Override    public boolean isFull() {        return top == maxTop - 1;    }    @SuppressWarnings("unchecked")    @Override    public T top() {        if (top == -1) {            System.out.println("Empty");            return null;        }        return (T) elementData[top];    }    @Override    public boolean push(T x) {        if (top == maxTop) {            System.err.println("Full");            return false;        }        elementData[++top] = x;        return true;    }    @SuppressWarnings("unchecked")    @Override    public T pop() {        if (top == -1) {            System.err.println("Empty");            return null;        }                T result = (T)elementData[top];        elementData[top] = null; //gc        top--;        return result;    }    @Override    public void clear() {                //let gc do its work        for(int i = 0; i < top+1; i++) {                        elementData[i] = null;        }                top = -1;    }}
public class StackCalc {    private SeqStack<Integer> stack;    public StackCalc(int maxSize) {        stack = new SeqStack<Integer>(maxSize);    }    private void pushOperand(Integer number) {        stack.push(number);    }    private Number doOperate(char oper) {        Integer right = stack.pop();        Integer left = stack.pop();        Integer result = null;        if (left != null && right != null) {            switch (oper) {            case ‘+‘:                result = left.intValue() + right.intValue();                break;            case ‘-‘:                result = left.intValue() - right.intValue();                break;            case ‘*‘:                result = left.intValue() * right.intValue();                break;            case ‘/‘:                if (right.intValue() == 0) {                    System.err.println("Divide by 0");                }                result = left.intValue() / right.intValue();                break;            default:                break;            }        }        stack.push(result);        return result;    }    private int icp(char c) {        switch (c) {        case ‘#‘:            return 0;        case ‘(‘:            return 7;        case ‘*‘:            return 4;        case ‘/‘:            return 4;        case ‘+‘:            return 2;        case ‘-‘:            return 2;        case ‘)‘:            return 1;        default:            return -1;        }    }    private int isp(int c) {        switch (c) {        case ‘#‘:            return 0;        case ‘(‘:            return 1;        case ‘*‘:            return 5;        case ‘/‘:            return 5;        case ‘+‘:            return 3;        case ‘-‘:            return 3;        case ‘)‘:            return 7;        default:            return -1;        }    }    public String transfer(String expression) {        StringBuilder sb = new StringBuilder();        SeqStack<Character> stack = new SeqStack<Character>(expression.length());        stack.push(‘#‘);        for (int i = 0; i < expression.length(); i++) {            Character c = expression.charAt(i);            if (‘0‘ <= c && c <= ‘9‘ || ‘a‘ <= c && c <= ‘z‘ ||                    ‘A‘ <= c && c <= ‘Z‘) { // digit character                sb.append(c);            } else { // 操作符                if (icp(c) > isp(stack.top())) { // 进栈                    stack.push(c);                } else { // 出栈                    if (c == ‘)‘) {                        char ch = stack.pop();                        while (ch != ‘(‘) {                            sb.append(ch);                            ch = stack.pop();                        }                    } else {                        char ch = stack.pop();                        while (icp(c) <= isp(ch)) {                            sb.append(ch);                            ch = stack.pop();                        }                        stack.push(ch);                        stack.push(c);                    }                }            }        } // end of for        char ch = stack.pop();        while (ch != ‘#‘) {                        sb.append(ch);            ch = stack.pop();        }        stack.clear();                return sb.toString();    }    public Integer calc(String expression) {        expression = transfer(expression);        for (int i = 0; i < expression.length(); i++) {            char c = expression.charAt(i);            switch (c) {            case ‘+‘:            case ‘-‘:            case ‘*‘:            case ‘/‘:                doOperate(c);                break;            default:                pushOperand(new Integer(c + ""));                break;            }        }        return stack.pop();    }    /**     * @param args     */    public static void main(String[] args) {        StackCalc calc = new StackCalc(10);        System.out.println(calc.calc("6/(4-2)+3*2"));    }}

 

java stack实现的中缀简单四则运算表达式计算