栈的应用

栈实现综合计算器
栈——使用栈完成计算一个表达式的结果

7 2 2-5+1-5+3 -4？

思路分析

栈的构建

//先创建一个栈
//定义一个ArrayStack2表示栈，需要扩展功能
class ArrayStack2{
    private int maxSize;  //栈的大小
    private int[] stack; //  用数组模拟栈，数据就放到该数组中
    private int top = -1;  //top表示栈顶，初始化为-1

    //构造器
    public ArrayStack2 ( int maxSize ) {
        this.maxSize = maxSize;
        stack = new int[ this.maxSize ];
    }

    //栈满
    public boolean isFull(){
        return top == maxSize - 1;
    }
    //栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈——push
    public void push ( int value ) {
        //先判断栈是否满
        if ( isFull ( ) ) {
            System.out.println ( "栈满" );
            return;
        }
        top++;
        stack[ top ] = value;
    }

    //出栈——pop,将栈顶数据返回
    public int  pop ( ) {
        if ( isEmpty ( ) ) {
            //抛出异常
            throw new RuntimeException ( "栈空，没有数据" );   //运行异常
        }
        int value = stack[ top ];
        top--;
        return value;
    }

    //遍历栈,遍历时从栈顶到栈底
    public void list ( ) {
        if ( isEmpty ( ) ) {
            System.out.println ("栈空没有数据~" );
            return;
        }
        for ( int i = top ; i >= 0 ; i-- ) {
            System.out.printf ( "stack[%d]=%d\n",i,stack[i]);
        }
    }

    //返回运算附的优先级，优先级使用数字表示，数字越大，表示优先级越高
    //局限，目前的表达式只有+、-、*、/
    public int priority ( int oper) {
        if ( oper == '*' || oper == '/' ) {
            return 1;
        }
        else if ( oper == '+'|| oper == '-' ) {
            return 0;
        }else{
            return -1;
        }
    }

    //判断是不是一个运算附
    public boolean isOper ( char oper ) {
        return oper == '+' || oper == '-' || oper == '*' || oper == '/';
    }

    //计算方法
    /**
     * @param num1  最先弹出的数
     * @param num2  第二个弹出的数
     * @param oper  弹出的运算符
     * @return  res 结果
     */
    public int cal ( int num1, int num2, int oper ) {
        int res=0; //res表示计算结果
        switch (oper){
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num2 * num1;
                break;
            case '/':
                res = num2 / num1;
                break;
        }
        return res;
    }

    //可以返回当前栈顶的值，单并不出栈
    public int peek(){
        return stack[ top ];
    }


}

实例应用

public class Calculator {
    public static void main ( String[] args ) {
        String expression = "7*2*2-5+1-5+3-4";   //中缀表达式
        //创建两个栈，数栈和符号栈
        ArrayStack2 numStack  = new ArrayStack2 ( 10 );
        ArrayStack2 operStack  = new ArrayStack2 ( 10 );
        //定义变量
        int index = 0;  //用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';  //将每次扫描的char保存到ch里
        String keepnum="";  //多位数
        //开始while语句，循环扫描expression
        while (true) {
            //依次得到expression的每一个字符
            ch = expression.substring ( index, index + 1 ).charAt ( 0 );  //取出一个字符串后，charAt取第一个字符
            //判断是否是数字还是字符，并做相应处理
            if ( operStack.isOper ( ch ) ) {  //如果是运算符
                //判断当前的符号栈是否为空
                if ( operStack.isEmpty ( ) ) {
                   //直接入
                    operStack.push ( ch );
                }
                else{
                    //判断优先级、

                    //如果当前的优先级小于或者等于栈中的操作符
                    //就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
                    //将得到结果，入数栈，然后将当前的操作符入符号栈
                    if ( operStack.priority ( ch ) <= operStack.priority ( operStack.peek ( ) ) ) {
                        num1 = numStack.pop ( );
                        num2 = numStack.pop ( );
                        oper=operStack.pop ( );
                        res = numStack.cal ( num1, num2, oper );
                        //把运算的结果入数栈
                        numStack.push ( res );
                        //然后把当前的符号入符号栈
                        operStack.push ( ch  );
                    }
                    //大于，直接入符号栈
                    else {
                        operStack.push ( ch );
                    }
                }

            }
            else {  //数字直接入栈
                //numStack.push ( ch-48 );  // '1'=49 而真实是1

                //处理多位数时，不能的发现是一个数就入栈，有可能是多位数
                //在处理数时，需要向expression的表达式的index后在看一位，如果是数进行扫描，如果不是数就停止
                //因此我们需要定义一个字符串变量，用于拼接

                keepnum+=ch;

                //判断ch是否是最后一个
                if ( index==expression.length()-1){
                    numStack.push ( Integer.parseInt ( keepnum ) );
                }else {
                    //判断下一个字符是不是数字，如果是数字就继续扫描
                    //index本身值不变
                    if ( operStack.isOper ( expression.substring ( index + 1, index + 2 ).charAt ( 0 ) ) ) {
                        numStack.push ( Integer.parseInt ( keepnum ) );  //Integer.parseInt ( keepnum )字符串转数字
                        //！！！重要 ,keepnum清空
                        keepnum = "";
                    }
                }

            }
            //让index+1，并判断是否到最后
            index++;
            if ( index >= expression.length ( ) ) {
                break;
            }


        }

        //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
        while (!operStack.isEmpty ()) {  //通过符号栈来判断数栈
            num1 = numStack.pop ( );
            num2 = numStack.pop ( );
            oper=operStack.pop ( );
            res = numStack.cal ( num1, num2, oper );
            numStack.push ( res );
        }
        //讲数栈的最后一个数pop出
        System.out.printf ("表达式 %s = %d",expression,numStack.pop ( ));



    }
}