数据结构和算法的学习笔记(第五部分)

简介: 自学的笔记

5.5 、栈实现综合计算器(中缀表达式)

使用栈来实现综合计算器

image-20221028123053510

思路分析(图解)

image-20221028125037591

  • 思路分析:如何使用栈完成计算一个表达式的结果?(由于原表达式过长,演示需要时间所以换成第二个表达式)
    • 1、通过一个index值(索引),来遍历我们的表达式
    • 2、如果发现是一个数字,就直接入数栈
    • 3、如果发现扫描到的是一个符号,就分成以下两种情况
      • 3.1、如果发现当前的符号栈为空,就直接入栈
      • 3.2、如果符号栈有操作符时,就与栈中的操作符进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,这时就需要从数栈中pop中两个数,再重符号栈中pop中符号(即运算符)进行运算,将得到的运行结果,入数栈,然后将当前的操作符入符号栈,如果当前的操作符的优先级大于栈中的操作符,就直接入栈(符号栈)。
    • 4、当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并运算
    • 5、最后数栈只有一个数组就是这个表达式的结果
  • 验证表达式:3+2*6-2 = ?

代码实现:[1. 先实现一位数的运算, 2. 扩展到多位数的运算]

  • 这里复用前面使用数组模拟栈的代码,并在原功能上进行加强
    • 即加上运算符优先级、判断是不是运算符和计算的方法
public 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;
    }

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

    //模拟出栈,将栈顶的数据返回
    public int pop() {
        //先判断栈是否空
        if (isEmpty()) {
            //抛出异常
            throw new RuntimeException("栈空,没有数据");
        }
        //先取得栈顶的值
        int value = stack[top];
        top--;
        return value;
    }

    //显示栈的情况(遍历栈),由于栈是先入后出,所以要从栈底开始遍历
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空,没有数据");
        }
        //需要从栈顶开始显示数据
        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 val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1,int num2,int oper){
        int result = 0;  //用于存放计算的结果
        switch (oper){
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num2 - num1;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num2 / num1;
                break;
        }
        return result;
    }
    //可以返回当前栈顶的值,但是不是真正的出栈
    public int peek(){
        return stack[top];
    }
}

接下来就开始测试了

public class Calculator {
    public static void main(String[] args) {
        //根据思路,完成表达式的运算
        String expression = "3+2*6-2";
        //创建两个栈,一个数栈一个符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        //定义需要的相关变量
        int index = 0; //用于扫描表达式中的数字和运算符
        int num1 = 0;    //计算的数字1
        int num2 = 0;    //计算的数字2
        int oper = 0;    //运算符
        int result = 0;  //接收结果
        char ch = ' '; //将每次扫描得到的char保存到ch中
        //开始使用while循环扫描expression
        while (true){
            //一次得到expression里的每一个字符
            ch = expression.substring(index,index+1).charAt(0);
            //判断ch是什么然后做相应的处理
            if (operStack.isOper(ch)){ //如果是运算符
                //判断当前符号栈是否为空
                if (!operStack.isEmpty()){
                    //如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符
                    if (operStack.priority(ch)<= operStack.priority(operStack.peek())){
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        result = numStack.cal(num1, num2,oper);
                        //把运算的结果入数栈
                        numStack.push(result);
                        //把当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        //如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈
                        operStack.push(ch);
                    }
                }else {
                    //如果为空直接入符号栈
                    operStack.push(ch);
                }
            }else { //如果是数,则直接入数栈
                numStack.push(ch-48);
            }
            //让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();
            result = numStack.cal(num1, num2,oper);
            numStack.push(result);  //入栈
        }
        //将数栈的最后数pop出来,就是结果
        int result2 = numStack.pop();
        System.out.printf("表达式%s = %d",expression,result2);
    }
}

经测试,完成了单位数运算

image-20221028152718823

但是又有一个新问题,即双位数参与运算就会导致运算结果不正确

image-20221028152828440

所以要对代码进行再次优化,即在扫描数时加上逻辑

else { //如果是数,则直接入数栈
                /*
                  numStack.push(ch-48);
                  分析思路
                  1、当处理多位数时,不能发现是一个数就立即入栈,因为它可能是多位数
                  2、在处理数时,需要向expression的表达式的后面index后再看一位,如果是数就继续扫描,如果是符号才入栈
                  3、因此我们需要定义一个字符串变量,用于拼接
                  处理多位数
                 */
                keepNum += ch;
                //如果ch以及是expression的最后一位,就直接入栈
                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));
                        //重要的清空,keepNum清空
                        keepNum = "";
                    }
                }
            }

5.6 、逆波兰计算器

我们完成一个逆波兰计算器,要求完成如下任务:

1) 输入一个逆波兰表达式(后缀表达式),使用栈(Stack), 计算其结果

2) 支持小括号和多位数整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算。

3) 思路分析

  • 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
  • 1.从左至右扫描,将 3 和 4 压入堆栈;
  • 2.遇到+运算符,因此弹出 4 和 3(4 为栈顶元素,3 为次顶元素),计算出 3+4 的值,得7,再将7 入栈;
  • 3.将 5 入栈;
  • 4.接下来是×运算符,因此弹出 5 和 7,计算出 7×5=35,将 35 入栈;
  • 5.将 6 入栈;
  • 6.最后是-运算符,计算出 35-6 的值,即 29,由此得出最终结果

4) 代码实现:

 public class PolandNotationStack {

    public static void main(String[] args) {
        //1、先定义一个逆波兰表达式, (3+4) * 5 -6 --> 3 4 + 5 * 6 - (使用空格隔开)
        String suffixExpression = "3 4 + 5 * 6 -";
        //测试结果
        List<String> list = getListString(suffixExpression);
        int result = calculate(list);
        System.out.println("计算的结果=" + result);
    }

    //2、定义一个方法,依次将数据和运算符放入 ArrayList中
    public static List<String> getListString(String suffixExpression) {
        //3、将逆波兰表达式进行分隔(即使用空格进行分隔)
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        //4、使用for循环对数组split进行遍历,每循环一次就取出字符串中的一个元素
        for (String ele : split) {
            list.add(ele);
        }
        //4.1、遍历完成后再将数组返回
        return list;
    }

    //4.2、创建一个栈
    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        //4.3、遍历
        for (String item : list) {
            //5.1、从左至右扫描,使用正则表达式取出数
            if (item.matches("\\d+")) {  //代表匹配的是多位数
                //5.2、扫描到元素内有数直接入栈
                stack.push(item);
            } else {
                //6、遇到运算符,因此pop栈顶元素和为次顶元素,计算出值
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = 0;  //6.1、定义一个存放结果的值
                if (item.equals("+")) { //加法
                    result = num1 + num2;
                } else if (item.equals("-")) { //减法
                    result = num1 - num2;
                } else if (item.equals("*")) { //乘法
                    result = num1 * num2;
                } else if (item.equals("/")) { //除法
                    result = num1 / num2;
                } else {
                    //若不是加减乘除就抛出异常
                    throw new RuntimeException("运算符有误");
                }
                //6.1、再将计算结果入栈
                stack.push(result + "");
            }
        }
        //7、最后留在栈中的数就是结果
        return Integer.parseInt(stack.pop());
    }
}

5.7 、中缀表达式转换为后缀表达式

后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将 中缀表达式转成后缀表达式。

5.7.1、具体步骤如下

  • 1) 初始化两个栈:运算符栈 s1 和储存中间结果的栈 s2;
  • 2) 从左至右扫描中缀表达式;
  • 3) 遇到操作数时,将其压 s2;
  • 4) 遇到运算符时,比较其与 s1 栈顶运算符的优先级:
    • 1.如果 s1 为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    • 2.否则,若优先级比栈顶运算符的高,也将运算符压入 s1;
    • 3.否则,将 s1 栈顶的运算符弹出并压入到 s2 中,再次转到(4-1)与 s1 中新的栈顶运算符相比较;
  • 5) 遇到括号时:
    • (1) 如果是左括号“(”,则直接压入 s1
    • (2) 如果是右括号“)”,则依次弹出 s1 栈顶的运算符,并压入 s2,直到遇到左括号为止,此时将这一对括号丢弃
  • 6) 重复步骤 2 至 5,直到表达式的最右边
  • 7) 将 s1 中剩余的运算符依次弹出并压入 s2 8) 依次弹出 s2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
  • 8) 依次弹出 s2 中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

5.7.2、举例说明:

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下 因此结果为 :"1 2 3 + 4 × + 5 –"

扫描到的元素 s2(栈底->栈顶) s1(栈底->栈顶) 说明
1 1 数组,直接入栈
+ 1 + s1为空,运算符直接入栈
1 +( 左括号,直接入栈
1 +(( 左括号,直接入栈
2 1 2 +(( 数字
+ 1 2 +((+ s1栈顶为左括号,运算符直接入栈
3 1 2 3 +((+ 数字
1 2 3 + +( 右括号,弹出运算符直至遇到左括号
* 1 2 3 + +( * s1栈顶为左括号,运算符直接入栈
4 1 2 3 + 4 +( * 数字
1 2 3 + 4 * + 右括号,弹出运算符直至遇到左括号
- 1 2 3 + 4 * + - - 于+ 优先级相同,因此弹出+,再压入 -
5 1 2 3 + 4 * +5 - 数字
到达最右端 1 2 3 + 4 * +5 - s1中剩余的运算符

5.7.3、代码实现中缀表达式转为后缀表达式

思路分析:

中缀表达式 1 + ( ( 2 + 3 )× 4) - 5 =》 后缀表达式

s2 出栈 - 5 + * 4 + 3 2 1 => 1 2 3 + 4 * + 5 -

中缀表达式 转 后缀表达式的 思路步骤分析

打比方 : 降龙十八掌 :学习 -》 应用 [层次]

算法 -》第一个层面: 理解算法-》灵活运用算法

第二层: 设计算法-》 运用 【】

1) 初始化两个栈:运算符栈s1和储存中间结果的栈s2;

2) 从左至右扫描中缀表达式;

3) 遇到操作数时,将其压s2;

4) 遇到运算符时,比较其与s1栈顶运算符的优先级:

1.如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

2.否则,若优先级比栈顶运算符的高,也将运算符压入s1;

3.否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较;

5) 遇到括号时:
(1) 如果是左括号“(”,则直接压入s1
(2) 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃

6) 重复步骤2至5,直到表达式的最右边

7) 将s1中剩余的运算符依次弹出并压入s2

8) 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

代码实现入下:

/**
 * 完成一个将中缀表达式转成后缀表达式的功能
 * 说明:1、1 +((2+3)* 4)-5 --> 转成 1 2 3 + 4 * + 5 -
 * 2、直接对字符串操作不方便,因此先将"1 +((2+3)* 4)-5"-->中缀表达式转换成对应的List
 * 即 "1 +((2+3)* 4)-5" --> ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
 */
public class PolandNotationStackTwo {
    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        //测试功能是否正常
        List<String> list = toInfixExpressionList(expression);
        System.out.println(list); //[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
    }

    //1、首先编写一个方法,将中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s) {
        //2、定义一个List,存放中缀表达式对应的内容
        List<String> list = new ArrayList<>();
        int i = 0; //用于遍历中缀表达式字符串
        String str; //用于对多位数的拼接
        char c; //每遍历到一个字符,就放入到c中
        do {
            //如果c是非数字,就需要加入到list中
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                i++;   //i需要后移
            } else {  //如果是一个数,需要考虑多位数的问题
                str = "";  //先将str置空
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;  //拼接
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;  //返回
    }
}

/**
 * description
 * 可以返回一个运算符对应的优先级
 *
 * @author
 * @since 2022/11/18 10:04
 */
public 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("不存在该运算符");
        }
        return result;
    }
}

/**
 * 完成一个将中缀表达式转成后缀表达式的功能
 * 说明:1、1 +((2+3)* 4)-5 --> 转成 1 2 3 + 4 * + 5 -
 * 2、直接对字符串操作不方便,因此先将"1 +((2+3)* 4)-5"-->中缀表达式转换成对应的List
 * 即 "1 +((2+3)* 4)-5" --> ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
 */
public class PolandNotationStackTwo {
    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        //测试功能是否正常
        List<String> list = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的List=" +list); //[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
        List<String> parseSuffixExpressionList = parseSuffixExpressionList(list);
        System.out.println("后缀表达式对应的List= "+ parseSuffixExpressionList);
    }

    //1、首先编写一个方法,将中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s) {
        //2、定义一个List,存放中缀表达式对应的内容
        List<String> list = new ArrayList<>();
        int i = 0; //用于遍历中缀表达式字符串
        String str; //用于对多位数的拼接
        char c; //每遍历到一个字符,就放入到c中
        do {
            //如果c是非数字,就需要加入到list中
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                i++;   //i需要后移
            } else {  //如果是一个数,需要考虑多位数的问题
                str = "";  //先将str置空
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;  //拼接
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;  //返回
    }

    //3、将得到的中缀表达式对应的List转成后缀表达式对应的List
    public static List<String> parseSuffixExpressionList(List<String> list) {
        //4、定义两个栈
        Stack<String> s1 = new Stack<>(); //符号栈
        //4.1、说明:因为s2在整个转换过程中没有pop操作,而且最后还需要逆序输出,因此为了简化使用List替代
        List<String> s2 = new ArrayList<String>(); //存放中间结果
        //5、遍历中缀表达式对应的List
        for (String item : list) {
            //6、如果是一个数,加入到s2,使用正则表达式判断是否是数
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                //6.1如果是左括号,直接入s1符号栈
                s1.push(item);
            } else if (item.equals(")")) {
                //6.2、 如果是右括号,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();  //将( 弹出 s1这个栈,消除小括号
            } else {
                //6.3、当item的优先级小于等于s1栈顶运算符的优先级,将s1栈顶的运算符弹出并加入到s2中,再次转到与s1中新的栈顶运算符相比较
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //6.4、还需要将item压入栈中
                s1.push(item);
            }
        }
        //7、将s1剩余的运算符依次弹出并加入s2中
        while (s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2;  //注意,因为是存放到List中,因此按顺序输出就是后缀表达式对应的List
    }
}
相关文章
|
22天前
|
存储 算法 Java
【数据结构与算法】1.数据结构绪论
【数据结构与算法】1.数据结构绪论
|
24天前
|
算法
【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法
【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法
26 0
|
24天前
|
搜索推荐 算法 大数据
【数据结构入门精讲 | 第十篇】考研408排序算法专项练习(二)
【数据结构入门精讲 | 第十篇】考研408排序算法专项练习(二)
20 0
|
24天前
|
存储 搜索推荐 算法
【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)
【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)
16 0
|
24天前
|
存储 搜索推荐 算法
【数据结构入门精讲 | 第八篇】一文讲清全部排序算法(2)
【数据结构入门精讲 | 第八篇】一文讲清全部排序算法(2)
18 0
|
24天前
|
搜索推荐 算法 Shell
【数据结构入门精讲 | 第七篇】一文讲清全部排序算法(1)
【数据结构入门精讲 | 第七篇】一文讲清全部排序算法(1)
15 0
|
1天前
|
存储
栈和队列OJ题
栈和队列OJ题
6 0
|
1天前
|
编译器 C++
队列实现栈VS栈实现队列
队列实现栈VS栈实现队列
6 0
|
1天前
【数组栈】实现
【数组栈】实现
5 0

相关产品