新星计划Day8【数据结构与算法】 栈Part2

新星计划Day8【数据结构与算法】 栈Part2

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

👕参考网课：尚硅谷

💻首发时间：🎞2022年5月2日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🛒导航小助手🎪

文章目录

👢036 前缀 中缀 后缀表达式规则

前缀表达式（波兰表达式）

• 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
• 举例说明：(3+4)*5-6 对应的前缀表达式就是 - * + 3 4 5 6

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

例如 (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

• 从右至左扫描，将6、5、4、3压入堆栈
• 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
• 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
• 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

中缀表达式

• 中缀表达式就是常见的运算表达式，如(3+4)*5-6
• 中缀表达式的求值是平常最为熟悉的，但是对计算机说却不好操作（前面我们将的案例就能看出这个问题，）因此，在计算结束时，往往会将中缀表达式转成其它表达式来操作（一般是转成后缀表达式）

后缀表达式

• 后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
• 中举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

后缀表达式的计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 -****, 针对后缀表达式求值步骤如下:

• 从左至右扫描，将3和4压入堆栈
• 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈
• 将5入栈
• 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈
• 将6入栈
• 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

🎎037 逆波兰计算器分析和实现（1）

• 输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
• 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
• 思路分析
• 代码完成

importjava.util.ArrayList;importjava.util.List;importjava.util.Stack;/**
 * @author wuyou
 */publicclassPolandNotation{publicstaticvoidmain(String[] args){// 定义一个逆波兰表达式// (3+4)*5-6 => 3 4 + 5 * 6 -String suffixExpression ="3 4 + 5 * 6 -";// 先将3 4 + 5 * 6 - 放入一个链表，配合栈完成计算List<String> listString =getListString(suffixExpression);System.out.println(calculate(listString));}/**
     * 将逆波兰表达式的数据和运算符依次放到ArrayList中
     * @param suffixExpression 逆波兰表达式
     * @return 链表
     */publicstaticList<String>getListString(String suffixExpression){// 将suffixExpression分割String[] split = suffixExpression.split(" ");List<String> list =newArrayList<>();for(String element : split){
            list.add(element);}return list;}/**
     * 计算逆波兰表达式最终结果
     * @param stringList 数据和运算符链表
     * @return 计算结果
     */publicstaticintcalculate(List<String> stringList){// 创建一个栈即可Stack<String> stack =newStack<>();// 遍历链表for(String element : stringList){// 使用正则表达式来取出数，匹配多位数if(element.matches("\\d+")){// 入栈
                stack.push(element);}else{// pop出两个数，并进行运算再入栈int num2 =Integer.parseInt(stack.pop());int num1 =Integer.parseInt(stack.pop());int res =0;if(element.equals("+")){
                    res = num1 + num2;}elseif(element.equals("-")){
                    res = num1 - num2;}elseif(element.equals("*")){
                    res = num1 * num2;}elseif(element.equals("/")){
                    res = num1 / num2;}else{thrownewRuntimeException("运算符有误");}// 把res 入栈
                stack.push(res +"");}}returnInteger.valueOf(stack.pop());}}

🧣039 中缀转后缀表达式思路分析

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

具体步骤如下:

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

🎃040 中缀转后缀表达式代码实现

/**
 * @author wuyou
 */publicclassCalculator{publicstaticvoidmain(String[] args){// 测试运算String expression1 ="33+2+2*6-2";String expression2 ="7*22*2-5+1-5+3-4";String expression3 ="4/2*3-4*2-3-99";String expression4 ="1*1*1*3*2/3";String expression5 ="11*1*1*3*2/3";String expression6 ="1000*23";// 创建两个栈：数栈、符号栈ListStack1 numStack =newListStack1(10);ListStack1 operationStack =newListStack1(10);test(expression1, numStack, operationStack);test(expression2, numStack, operationStack);test(expression3, numStack, operationStack);test(expression4, numStack, operationStack);test(expression5, numStack, operationStack);test(expression6, numStack, operationStack);}/**
     * 测试方法，测试表达式的结果，并且打印结果
     * @param expression 表达式
     * @param numStack 数字栈
     * @param operationStack 符号栈
     */publicstaticvoidtest(String expression,ListStack1 numStack,ListStack1 operationStack){// 用于扫描int index =0;// 将每次扫描得到的char保存到chchar ch =' ';// 开始while循环的扫描expressionwhile(true){// 依次得到expression的每一个字符
            ch =getCharByIndex(expression, index);// 判断ch是什么，然后做相应的处理if(isOperation(ch)){// 运用管道过滤器风格，处理运算符operationSolve1(ch, numStack, operationStack);}else{// 数直接入数栈，对值为ASCII值-48// 当处理多位数时候，不能立即入栈，可能是多位数，调用过滤器处理多位数
                index =numSolve1(expression, index, numStack);}// 让index+1，并判断是否扫描到expression最后
            index++;if(index >=  expression.length()){break;}}// 最后只剩下两个数和一个运算符int res =cal((int) numStack.pop(),(int) numStack.pop(),(char) operationStack.pop());System.out.printf("表达式: %s = %d\n", expression, res);}/**
     * 获取表达式的下标位置为index的字符
     * @param expression 表达式
     * @param index 下标
     * @return
     */publicstaticchargetCharByIndex(String expression,int index){return expression.charAt(index);}/**
     * 处理数字入栈的情况，包含处理多位数的情况，并且返回到操作表达式当前的下标
     * @param expression 表达式
     * @param index 下标
     * @param numStack 数字栈
     * @return 新的下标
     */publicstaticintnumSolve1(String expression,Integer index,ListStack1 numStack){int end = index +1;for(; end < expression.length(); end++){char ch =getCharByIndex(expression, end);// 判断是不是数字if(!isOperation(ch)){continue;}else{break;}}String numStr = expression.substring(index, end);// 数据入栈
        numStack.push(Integer.valueOf(numStr));// 因为test函数进行了+1，所以这里进行-1，避免给重复添加return end -1;}/**
     * 符号过滤器1，判断当前是否具有字符
     * @param ch 运算符
     * @param numStack 数字栈
     * @param operationStack 运算符栈
     */publicstaticvoidoperationSolve1(char ch,ListStack1 numStack,ListStack1 operationStack){// 判断当前符号栈是否具有操作符if(!operationStack.isEmpty()){operationSolve2(ch, numStack, operationStack);return;}else{
            operationStack.push(ch);return;}}/**
     * 符号过滤器2，处理字符优先级，递归调用过滤器1
     * @param ch 运算符
     * @param numStack 数字栈
     * @param operationStack 运算符栈
     */publicstaticvoidoperationSolve2(char ch,ListStack1 numStack,ListStack1 operationStack){// 比较优先级if(priority(ch)<=priority((Character) operationStack.peek())){// 调用过滤器3进行计算operationSolve3(numStack,operationStack);// 递归调用过滤器1，不能递归调用过滤器2，因为可能存在当前运算符栈为空的情况operationSolve1(ch, numStack, operationStack);return;}else{// 直接将运算符加入到运算符栈中
            operationStack.push(ch);return;}}/**
     * 符号过滤器3，进行运算
     * @param numStack 数字栈
     * @param operationStack 运算符栈
     */publicstaticvoidoperationSolve3(ListStack1 numStack,ListStack1 operationStack){// 定义相关变量int num1 =(int) numStack.pop();int num2 =(int) numStack.pop();char operation =(char) operationStack.pop();int res =cal(num1, num2, operation);// 把运算结果加到数栈
        numStack.push(res);return;}/**
     * 返回运算符的优先级，数字越大，运算符越高
     * @param operation 运算符
     * @return
     */publicstaticintpriority(char operation){if(operation =='*'|| operation =='/'){return1;}elseif(operation =='+'|| operation =='-'){return0;}else{// 假设目前的表达式只有 + - * /return-1;}}/**
     * 判断是不是运算符
     * @param val 字符
     * @return 是不是运算符
     */publicstaticbooleanisOperation(char val){return val =='+'|| val =='-'|| val =='*'|| val =='/';}/**
     * 计算结果
     * @param num1 操作数1，先出栈的数
     * @param num2 操作数2，后出栈的数
     * @param operation 操作符
     * @return 计算结果
     */publicstaticintcal(int num1,int num2,char operation){// 用于存放运算的结果int res =0;switch(operation){case'+':
                res = num1 + num2;break;case'-':// num1是先弹出来的数，为被减数
                res = num2 - num1;break;case'*':
                res = num1 * num2;break;case'/':// num1是先弹出来的数，为被除数
                res = num2 / num1;default:break;}return res;}}/**
 * 表示链表的一个节点
 */classNode1{Object element;Node1 next;publicNode1(Object element){this(element,null);}/**
     * 头插法插入节点
     * @param element 新增节点的value
     * @param n 原来的头节点
     */publicNode1(Object element,Node1 n){this.element = element;
        next = n;}publicObjectgetElement(){return element;}publicvoidsetElement(Object element){this.element = element;}publicNode1getNext(){return next;}publicvoidsetNext(Node1 next){this.next = next;}}/**
 * 用链表实现堆栈
 */classListStack1{/**
     * 栈顶元素
     */Node1 header;/**
     * 栈内元素个数
     */int elementCount;/**
     * 栈的大小
     */int size;/**
     * 构造函数，构造一个空的堆栈
     */publicListStack1(){
        header =null;
        elementCount =0;
        size =0;}/**
     * 通过构造器 自定义栈的大小
     * @param size 栈的大小
     */publicListStack1(int size){
        header =null;
        elementCount =0;this.size = size;}/**
     * 设置堆栈大小
     * @param size 堆栈大小
     */publicvoidsetSize(int size){this.size = size;}/**
     * 设置栈顶元素
     * @param header 栈顶元素
     */publicvoidsetHeader(Node1 header){this.header = header;}/**
     * 获取堆栈长度
     * @return 堆栈长度
     */publicintgetSize(){return size;}/**
     * 返回栈中元素的个数
     * @return 栈中元素的个数
     */publicintgetElementCount(){return elementCount;}/**
     * 判断栈是否为空
     * @return 如果栈是空的，返回真，否则，返回假
     */publicbooleanisEmpty(){if(elementCount ==0){returntrue;}returnfalse;}/**
     * 判断栈满
     * @return 如果栈是满的，返回真，否则，返回假
     */publicbooleanisFull(){if(elementCount == size){returntrue;}returnfalse;}/**
     * 把对象入栈
     * @param value 对象
     */publicvoidpush(Object value){if(this.isFull()){thrownewRuntimeException("Stack is Full");}
        header =newNode1(value, header);
        elementCount++;}/**
     * 出栈，并返回被出栈的元素
     * @return 被出栈的元素
     */publicObjectpop(){if(this.isEmpty()){thrownewRuntimeException("Stack is empty");}Object obj = header.getElement();
        header = header.getNext();
        elementCount--;return obj;}/**
     * 返回栈顶元素
     * @return 栈顶元素
     */publicObjectpeek(){if(this.isEmpty()){thrownewRuntimeException("Stack is empty");}return header.getElement();}}

🏅042 完整版逆波兰计算器

完整版的逆波兰计算器，功能包括如下：

• 支持 + - * / ( )
• 多位数，支持小数
• 兼容处理, 过滤任何空白字符，包括空格、制表符、换页符

packagecom.atguigu.reversepolishcal;importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;importjava.util.Stack;importjava.util.regex.Pattern;publicclassReversePolishMultiCalc{/**
     * 匹配 + - * / ( ) 运算符
     */staticfinalString SYMBOL ="\\+|-|\\*|/|\\(|\\)";staticfinalString LEFT ="(";staticfinalString RIGHT =")";staticfinalString ADD ="+";staticfinalString MINUS ="-";staticfinalString TIMES ="*";staticfinalString DIVISION ="/";/**
     * 加減 + -
     */staticfinalint LEVEL_01 =1;/**
     * 乘除 * /
     */staticfinalint LEVEL_02 =2;/**
     * 括号
     */staticfinalint LEVEL_HIGH =Integer.MAX_VALUE;staticStack<String> stack =newStack<>();staticList<String> data =Collections.synchronizedList(newArrayList<String>());/**
     * 去除所有空白符
     *
     * @param s
     * @return
     */publicstaticStringreplaceAllBlank(String s){//  \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]return s.replaceAll("\\s+","");}/**
     * 判断是不是数字 int double long float
     *
     * @param s
     * @return
     */publicstaticbooleanisNumber(String s){Pattern pattern =Pattern.compile("^[-\\+]?[.\\d]*$");return pattern.matcher(s).matches();}/**
     * 判断是不是运算符
     *
     * @param s
     * @return
     */publicstaticbooleanisSymbol(String s){return s.matches(SYMBOL);}/**
     * 匹配运算等级
     *
     * @param s
     * @return
     */publicstaticintcalcLevel(String s){if("+".equals(s)||"-".equals(s)){return LEVEL_01;}elseif("*".equals(s)||"/".equals(s)){return LEVEL_02;}return LEVEL_HIGH;}/**
     * 匹配
     *
     * @param s
     * @throws Exception
     */publicstaticList<String>doMatch(String s)throwsException{if(s ==null||"".equals(s.trim()))thrownewRuntimeException("data is empty");if(!isNumber(s.charAt(0)+""))thrownewRuntimeException("data illeagle,start not with a number");

        s =replaceAllBlank(s);String each;int start =0;for(int i =0; i < s.length(); i++){if(isSymbol(s.charAt(i)+"")){
                each = s.charAt(i)+"";// 栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈if(stack.isEmpty()|| LEFT.equals(each)||((calcLevel(each)>calcLevel(stack.peek()))&&calcLevel(each)< LEVEL_HIGH)){
                    stack.push(each);}elseif(!stack.isEmpty()&&calcLevel(each)<=calcLevel(stack.peek())){// 栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈while(!stack.isEmpty()&&calcLevel(each)<=calcLevel(stack.peek())){if(calcLevel(stack.peek())== LEVEL_HIGH){break;}
                        data.add(stack.pop());}
                    stack.push(each);}elseif(RIGHT.equals(each)){//  ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈while(!stack.isEmpty()&& LEVEL_HIGH >=calcLevel(stack.peek())){if(LEVEL_HIGH ==calcLevel(stack.peek())){
                            stack.pop();break;}
                        data.add(stack.pop());}}
                start = i;// 前一个运算符的位置}elseif(i == s.length()-1||isSymbol(s.charAt(i +1)+"")){
                each = start ==0? s.substring(start, i +1): s.substring(start +1, i +1);if(isNumber(each)){
                    data.add(each);continue;}thrownewRuntimeException("data not match number");}}// 如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列Collections.reverse(stack);
        data.addAll(newArrayList<>(stack));System.out.println(data);return data;}/**
     * 算出结果
     *
     * @param list
     * @return
     */publicstaticDoubledoCalc(List<String> list){Double d =0d;if(list ==null|| list.isEmpty()){returnnull;}if(list.size()==1){System.out.println(list);
            d =Double.valueOf(list.get(0));return d;}ArrayList<String> list1 =newArrayList<>();for(int i =0; i < list.size(); i++){
            list1.add(list.get(i));if(isSymbol(list.get(i))){Double d1 =doTheMath(list.get(i -2), list.get(i -1), list.get(i));
                list1.remove(i);
                list1.remove(i -1);
                list1.set(i -2, d1 +"");
                list1.addAll(list.subList(i +1, list.size()));break;}}doCalc(list1);return d;}/**
     * 运算
     *
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */publicstaticDoubledoTheMath(String s1,String s2,String symbol){Double result;switch(symbol){case ADD:
                result =Double.valueOf(s1)+Double.valueOf(s2);break;case MINUS:
                result =Double.valueOf(s1)-Double.valueOf(s2);break;case TIMES:
                result =Double.valueOf(s1)*Double.valueOf(s2);break;case DIVISION:
                result =Double.valueOf(s1)/Double.valueOf(s2);break;default:
                result =null;}return result;}publicstaticvoidmain(String[] args){// String math = "9+(3-1)*3+10/2";String math ="12.8 + (2 - 3.55)*4+10/5.0";try{doCalc(doMatch(math));}catch(Exception e){
            e.printStackTrace();}}}

下期预告：力扣每日一练之二维数组上篇Day4

觉得文章写的不错的亲亲们，点赞评论走一波，爱你们哦！🥗