D3-栈[Java数据结构和算法]

package cn.atguigu.stack;

import java.util.Scanner;

public class ArrayStackDemo {

    public static void main(String[] args)throws Exception {
        // TODO Auto-generated method stub
        //创建对象
        ArrayStack arrayStack=new ArrayStack(4);
        String key="";
        boolean loop=true;//控制是否需要退出菜单
        Scanner scanner=new Scanner(System.in);
        
        while(loop) {
            System.out.println("show:表示显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:入栈");
            System.out.println("pop:出栈");
            key=scanner.next();
            switch(key) {
            case "show":
                arrayStack.list();
                break;
            case "push":
                System.out.println("请输入一个数：");
                int value=scanner.nextInt();
                arrayStack.push(value);
                break;
            case "pop":
                System.out.println("出栈的数字为:");
                System.out.println(arrayStack.pop());
                break;
            case "exit":
                scanner.close();
                loop=false;
                break;
            }
        }
        System.out.println("程序退出");
    }

}

//定义ArrayStack表示栈
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack;//数组，数组模拟栈，数据就放在数组中
    private int top=-1;//top表示栈顶，初始化为-1
    //构造器
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack =new int[maxSize];
    }
    //判断栈是否满
    public boolean isFull() {
        return top==maxSize-1;
    }
    //判断栈空
    public boolean isEmpty() {
        return top==-1;
    }
    //进栈
    public void push(int value) {
        if(isFull()) {
            System.out.println("栈满，无法输入");
            return;
        }
        top++;
        stack[top]=value;
    }
    //出栈
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("栈空，没有数据");
        }
        int value=stack[top];
        top--;
        return top;
    }
    //显示栈的情况,遍历时，需要从栈顶开始显示数据
    public void list() {
        if(isEmpty()) {
            System.out.println("栈空，没有数据~~~");
            return;
        }
        //需要从栈顶开始显示数据
        for(int i=top;i>=0;i--) {
            System.out.printf("stack[%d]=%dn",i,stack[i]);
        }
    }
    
}

package cn.atguigu.stack;

public class Calculator {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String expression="30+2*6-2";
        //创建两个栈，一个为数栈，一个为符号栈
        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循环的扫描experession
        while(true) {
            //依次得到每一个字符
            ch=expression.substring(index,index+1).charAt(0);
            //判断ch是什么，然后做相应的处理
            if(operstack.isOperation(ch)) {//如果ch是运算符
                if(operstack.isEmpty()) {//如果operStack为空，直接存入
                    operstack.push(ch);//直接存入
                }else{//如果operStack不为空，需要再判断
                    if(operstack.priority(ch)>operstack.priority(operstack.peek())){
                        //若当前优先级别高于栈中的操作符，直接入栈
                        operstack.push(ch);//再将当前操作符入栈
                    }else {//否则，取出两个数字，进行计算
                        num1=numstack.pop();
                        num2=numstack.pop();
                        oper=operstack.pop();
                        res=numstack.cal(num1,num2,oper);
                        numstack.push(res);//将计算结果入栈
                        operstack.push(ch);//将当前运算符入栈
                    }
                }
            }else {//如果不是运算符，直接入numStack栈
                //分析思路
                //1.当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                //2.在处理数，需要向expression的表达式index后再看以为，如果是数就进行扫描，如果是符号才进行入栈
                //3.定义字符串变量，用于拼接
                //处理多位数
                keepNum+=ch;
                //若ch已经是expression的最后一位就直接入栈
                if(index==expression.length()-1) {
                    numstack.push(Integer.parseInt(keepNum));                    
                }else {
                    //判断下一个字符是不是数字，如果是继续扫描
                    if(operstack.isOperation(expression.substring(index+1,index+2).charAt(0))) {
                        //如果后一位是运算符，入栈keepNum="1"或"123"
                        numstack.push(Integer.parseInt(keepNum));
                        //清空
                        keepNum="";
                    }                    
                }
            }
            //让index加1，并单独按是否扫描到expression最后
            index++;
            if(index>=expression.length()){
                break;
            }
        }
        
        //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号
        while(true) {
            //若符号栈为空，则计算到最后，数栈中只有一个数字
            if(operstack.isEmpty()) {
                break;
            }
            num1=numstack.pop();
            num2=numstack.pop();
            oper=operstack.pop();
            res=numstack.cal(num1,oper);
            numstack.push(res);
        }
        
        System.out.printf("表达式%s=%d",expression,numstack.pop());
}
}
//先创建一个数组
class ArrayStack2{
    private int maxSize;//栈的大小
    private int[] stack;//数组，数组模拟栈，数据就放在数组中
    private int top=-1;//top表示栈顶，初始化为-1
    //构造器
    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack =new int[maxSize];
    }
    //该方法可以返回当前栈顶的值，但是不是真正的pop
    public int peek() {
        return stack[top];
    }
    //判断栈是否满
    public boolean isFull() {
        return top==maxSize-1;
    }
    //判断栈空
    public boolean isEmpty() {
        return top==-1;
    }
    //进栈
    public void push(int value) {
        if(isFull()) {
            System.out.println("栈满，无法输入");
            return;
        }
        top++;
        stack[top]=value;
    }
    //出栈
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("栈空，没有数据");
        }
        int value=stack[top];
        top--;
        return value;
    }
    //显示栈的情况,stack[i]);
        }
    }
    //返回运算符的优先级，优先级由程序员来确定，优先级使用数字表示
    //数字越大，则优先级越高
    public int priority(int oper) {
        if(oper==‘*‘||oper==‘/‘) {
            return 1;
        }else if(oper==‘+‘||oper==‘-‘) {
            return 0;
        }else {
            return -1;//默认只有加减乘除
        }
    }
    
    //判断是不是一个运算符
    public boolean isOperation(char val) {
        return (val==‘*‘||val==‘/‘||val==‘+‘||val==‘-‘);
    }
    //计算方法
    public int cal(int num1,int num2,int oper) {
        int res=0;//存放结果
        switch(oper) {
        case ‘+‘:
            res=num1+num2;break;
        case ‘-‘:
            res=num2-num1;break;
        case ‘*‘:
            res=num1*num2;break;
        case ‘/‘:
            res=num2/num1;break;
        default:break;
        }
        return res;
    }
}

package cn.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //先定义逆波兰表达式
        //(3+4)*5-6--> 3 4 + 5 * 6 -
        //说明：为了方便，逆波兰表达式中的数字和符号使用空格隔开
        String suffixExpression="3 4 + 5 * 6 -";
        //思路
        //1.先将表达式放入ArrayList中
        //2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
        List<String> rpnlist=getListString(suffixExpression);
        System.out.println(rpnlist);
        
        int res=calculate(rpnlist);
        System.out.println(res);
    }
//将一个逆波兰表达式，依次将数据和运算符放入到 ArrayList找那个
    public static List<String> getListString(String suffixExpression){
        //将suffixExpression分割
        String[] split=suffixExpression.split(" ");
        List<String> list=new ArrayList<String>();
        for(String ele:split) {
            list.add(ele);
        }
        return list;
    }
    //完成对逆波兰表达式的运算
    public static int calculate(List<String> ls) {
        //创建栈，只需要一个栈即可
        Stack<String> stack=new Stack<String>();
        //遍历ls
        for(String item:ls) {
            //使用正则表达式取出数
            if(item.matches("d+")) {//匹配的是多位数
                //入栈
                stack.push(item);
            }else {
                //pop出两个数，并运算，再入栈
                int num2=Integer.parseInt(stack.pop());
                int num1=Integer.parseInt(stack.pop());
                int res=0;
                if(item.equals("+")) {
                    res=num1+num2;
                }else if(item.equals("-")) {
                    res=num1-num2;
                }else if(item.equals("*")) {
                    res=num1*num2;
                }else if(item.equals("/")) {
                    res=num1/num2;
                }else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(res+"");
            }
        }
        //最后留在stack中的数据就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

package cn.atguigu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {

    //完成讲一个中缀表达式转成后缀表达式的功能
    //说明
    //1.(3+4)*5-6--> 3 4 + 5 * 6 -
    //2.因为直接对字符串进行操作，不方便，因此先将字符串准成中缀的表达式对应的List
//    String expression="(3+4)*5-6";
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //先定义逆波兰表达式
        //(3+4)*5-6--> 3 4 + 5 * 6 -
        //说明：为了方便，逆波兰表达式中的数字和符号使用空格隔开
        
         String suffixExpression="3 4 + 5 * 6 -"; String Expression="1+((2+3)*4)-5";
         List<String> infixExpressionList=toInfixExpressionList(Expression);
         System.out.println("中缀表达式List="+infixExpressionList);
         List<String> parseSuffixExpressionList=parseSuffixExpression(infixExpressionList);
         System.out.println("后缀表达式List="+parseSuffixExpressionList);
         int res=calculate(parseSuffixExpressionList); 
         System.out.println("结果为="+res);
         /* 
         * //思路 //1.先将表达式放入ArrayList中 //2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
         * List<String> rpnlist=getListString(suffixExpression);
         * System.out.println(rpnlist);
         * 
         */    }
    
    //将得到的中缀表达式对应的list-->后缀表达式对应的list
    public static List<String> parseSuffixExpression(List<String> ls){
        //定义两个栈
        Stack<String> s1=new Stack<String>();//符号栈
        //因为s2栈在整个转换过程中，没有pop操作，而且在后续过程中需要逆序输出
        //直接使用List<String>代替Stack<String>
        List<String> s2=new ArrayList<String>();//存储中间结果的s2
        //遍历ls
        for(String item:ls) {
            //如果是一个数，加入s2
            if(item.matches("d+")) {
                s2.add(item);
            }else if(item.equals("(")) {
                s1.push(item);
            }else if(item.equals(")")) {
                //如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时这一对括号抛弃
                while(!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();//将左括号弹出，消除小括号
            }else {
                //当item的优先级小于等于栈顶，将s1栈顶运算符弹出并加入到s2中，再次转到4.1与s1中新的栈顶运算符相比较
                while(s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //还需要将item压入栈
                s1.push(item);
            }
        }
        
        //将s1中剩余的运算符弹出并加入到s2
        while(s1.size()!=0) {
            s2.add(s1.pop());
        }
        return s2;//存放List，因此按顺序输出就是逆波兰表达式
    }
    //将中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s){
        //定义一个List，存放中缀表达式，对应的内容
        List<String> ls=new ArrayList<String>();
        int i=0;//指针，用于遍历中缀表达式字符串
        String str;//对多位数进行拼接
        char c;//每遍历到一个字符，就放入到c
        do {
            //如果c是一个非数字，需要加入到ls中去
            if((c=s.charAt(i))<48||(c=s.charAt(i))>57) {
                ls.add(""+c);
                i++;
            }else {
                //如果是一个数，需要考虑多位数
                str="";//先将str置成空串
                while(i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57) {
                    str+=c;//拼接
                    i++;
                }
                ls.add(str);
            }
        }while(i<s.length());
        return ls;
    }
    
//将一个逆波兰表达式，依次将数据和运算符放入到 ArrayList
    public static List<String> getListString(String suffixExpression){
        //将suffixExpression分割
        String[] split=suffixExpression.split(" ");
        List<String> list=new ArrayList<String>();
        for(String ele:split) {
            list.add(ele);
        }
        return list;
    }
    //完成对逆波兰表达式的运算
    public static int calculate(List<String> ls) {
        //创建栈，只需要一个栈即可
        Stack<String> stack=new Stack<String>();
        //遍历ls
        for(String item:ls) {
            //使用正则表达式取出数
            if(item.matches("d+")) {//匹配的是多位数
                //入栈
                stack.push(item);
            }else {
                //pop出两个数，并运算，再入栈
                int num2=Integer.parseInt(stack.pop());
                int num1=Integer.parseInt(stack.pop());
                int res=0;
                if(item.equals("+")) {
                    res=num1+num2;
                }else if(item.equals("-")) {
                    res=num1-num2;
                }else if(item.equals("*")) {
                    res=num1*num2;
                }else if(item.equals("/")) {
                    res=num1/num2;
                }else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push(res+"");
            }
        }
        //最后留在stack中的数据就是运算结果
        return Integer.parseInt(stack.pop());
    }
}

//编写一个类Operation 可以返回一个运算符对应的优先级
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;
    
    //返回对应的优先级数字
    public static int getValue(String operation) {
        int result=0;
        switch(operation) {
        case "+":
            result=ADD;
            break;
        case "-":
            result=SUB;
            break;
        case "*":
            result=MUL;
            break;
        case "/":
            result=DIV;
            break;
        default:
            System.out.println("不存在该运算符");
            break;    
        }
        return result;
    }
}