数据结构之使用栈实现计算器（加减乘除）

package com.ws.栈.栈计算器;

import java.util.Scanner;

public class Calculator {
    public static void main(String[] args) {
        String string;
        System.out.println("输入一个算术式：");
        Scanner scanner=new Scanner(System.in);
        string=scanner.next();
        //创建两个栈，一个数栈，一个符号栈
        ArrayStack shuStack=new ArrayStack(10);
        ArrayStack operStack=new ArrayStack(10);
        //定义相关变量
        int list=0;//用于扫描
        int shu1=0;//出栈数1
        int shu2=0;//出栈数2
        int oper=0;//操作符
        int jeiguo=0;//运算结果
        char ch=' ';//将每次扫描得到的char保存到ch
        String pinjeshu = "";//用于多位数拼接
        //循环扫描算数式
        while (true){
            //依次得到算术式的每一个字符
            ch=string.substring(list,list+1).charAt(0);
            //判断ch是什么，然后进行相应处理
            if (operStack.ifOper(ch)){//是运算符
                //判断当前的符号栈是否为空
                if (!operStack.ifFull()){//不为空处理
                    //如果符号栈不为空，就比较优先级，如果当前操作符优先级<=栈中操作符
                    if (operStack.printyouji(ch)<=operStack.printyouji(operStack.topkan())){
                        //从数栈出两个数，从符号栈出一个符号进行计算
                        shu1=shuStack.pop();
                        shu2=shuStack.pop();
                        oper=operStack.pop();
                        jeiguo=shuStack.suan(shu1,shu2,oper);
                        //把运算结果入数栈
                        shuStack.add(jeiguo);
                        //把当前操作符入符号栈
                        operStack.add(ch);
                    }else {//当前操作符优先级>=栈中优先级
                        operStack.add(ch);
                    }
                }else {//为空就直接入符号栈
                    operStack.add(ch);
                }
            }
            else {//数字入数栈
//                shuStack.add(ch-48);//看编码表可知，48  直接入数栈
                //1.处理多位数事不能直接入数栈，可能是多位数
                //2.处理数要看算术式字符串看下一位，数就继续扫描，是符号就入栈
                      //如果是最后一位就直接入数栈
                //3.定义字符串变量用于拼接

                //处理多位数
                pinjeshu+=ch;
                if (list==string.length()-1){ //如果是最后一位就直接入数栈
                    shuStack.add(Integer.parseInt(pinjeshu));
                }else {
                    //判断下一个字符是否是数字,是数字就继续扫描，运算符就入栈,看后面一位，不是list后移
                    if (shuStack.ifOper(string.substring(list + 1, list + 2).charAt(0))) {
                        //后一位是运算符就入栈
                        shuStack.add(Integer.parseInt(pinjeshu));//pinjeshu是“1”或者“123”样的字符串，需要转换成一个字符
                        //清空拼接
                        pinjeshu = "";
                    }
                }
            }
            //让字符+1，并判断算术式是否扫描到最后,就结束
            list++;
            if (list>=string.length()){
                break;
            }
        }
        //当算数式扫描到最后就顺序从数栈和符号栈中出栈，并计算
        while (true){
            //如果符号栈为空就得到最后结果,数栈中只有一个数字就是结果
            if (operStack.ifFull()){
                break;
            }
            //否则就
            //从数栈出两个数，从符号栈出一个符号进行计算
            shu1=shuStack.pop();
            shu2=shuStack.pop();
            oper=operStack.pop();
            jeiguo=shuStack.suan(shu1,shu2,oper);
            //把运算结果入数栈
            shuStack.add(jeiguo);
        }
        //将数栈出栈就是结果
        System.out.printf("表达式%s=%d\n",string,shuStack.pop());

    }
}

//创建栈
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack;//数组，模拟栈
    private int top=-1;//栈顶，初始化-1

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

    //判断栈满
    public boolean ifMax(){
        return top==maxSize-1;//数组下标从0开始，-1
    }

    //判断栈空
    public boolean ifFull(){
        return top==-1;
    }

    //入栈
    public void add(int value){
        //判断栈满
        if (ifMax()){
            System.out.println("栈满");
            return;
        }
        //入栈
        top++;
        stack[top]=value;
    }

    //出栈
    public int pop(){
        //判断栈是否为空
        if (ifFull()){
            //抛出异常
            throw new RuntimeException("栈空");
        }
        //出栈
        int value=stack[top];//先保存栈顶
        top--;//栈顶下移
        return value;
    }

    //遍历栈
    //栈顶开始显示数据
    public void list(){
        //判断栈空
        if (ifFull()){
            System.out.println("栈空");
            return;
        }
        //栈顶开始显示数据
        for (int i=top;i>=0;i--){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    //返回运算符的优先级，由程序员来确定,数字越大，优先级越高
    public int printyouji(int oper){
        if (oper=='*'||oper=='/'){
            return 1;
        }else if (oper=='+'||oper=='-'){
            return 0;
        }else {
            return -1;//假定只有+-*/
        }
    }
    //判断是不是一个运算符
    public boolean ifOper(char val){
        return val=='+'||val=='-'||val=='*'||val=='/';
    }
    //计算方法
    public int suan(int shu1,int shu2,int oper){
        int jieguo=0;//用于存放结果
        switch (oper){
            case '+':
                jieguo=shu1+shu2;
                break;
            case '-':
                jieguo=shu2-shu1;//注意顺序
                break;
            case '*':
                jieguo=shu1*shu2;
                break;
            case '/':
                jieguo=shu2/shu1;
            default:
                break;
        }
        return jieguo;
    }
    //返回当前栈顶的值，不出栈
    public int topkan(){
        return stack[top];
    }
}