博客主页:京与旧铺的博客主页
✨欢迎关注点赞收藏⭐留言✒
本文由京与旧铺原创,csdn首发!
系列专栏:java学习
参考网课:尚硅谷
首发时间:2022年5月2日
你做三四月的事,八九月就会有答案,一起加油吧
如果觉得博主的文章还不错的话,请三连支持一下博主哦
最后的话,作者是一个新人,在很多方面还做的不好,欢迎大佬指正,一起学习哦,冲冲冲
导航小助手 文章目录
- 新星计划Day8【数据结构与算法】 栈Part2
- 导航小助手
- @[toc]
- 036 前缀 中缀 后缀表达式规则
- 037 逆波兰计算器分析和实现(1)
- 泥039 中缀转后缀表达式思路分析
- 040 中缀转后缀表达式代码实现
- 042 完整版逆波兰计算器
前缀表达式(波兰表达式)
- 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
- 举例说明:(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,由此得出最终结果
- 输入一个逆波兰表达式(后缀表达式),使用栈(Stack), 计算其结果
- 支持小括号和多位数整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算。
- 思路分析
- 代码完成
import java.util.ArrayList; import java.util.List; import java.util.Stack; public class PolandNotation { public static void main(String[] args) { // 定义一个逆波兰表达式 // (3+4)*5-6 => 3 4 + 5 * 6 - String suffixExpression = "3 4 + 5 * 6 -"; // 先将3 4 + 5 * 6 - 放入一个链表,配合栈完成计算 List泥039 中缀转后缀表达式思路分析listString = getListString(suffixExpression); System.out.println(calculate(listString)); } public static List getListString(String suffixExpression) { // 将suffixExpression分割 String[] split = suffixExpression.split(" "); List list = new ArrayList<>(); for (String element : split) { list.add(element); } return list; } public static int calculate(List stringList) { // 创建一个栈即可 Stack stack = new Stack<>(); // 遍历链表 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; } else if (element.equals("-")) { res = num1 - num2; } else if (element.equals("*")) { res = num1 * num2; } else if (element.equals("/")) { res = num1 / num2; } else { throw new RuntimeException("运算符有误"); } // 把res 入栈 stack.push(res + ""); } } return Integer.valueOf(stack.pop()); } }
后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将 中缀表达式转成后缀表达式。
具体步骤如下:
- 初始化两个栈:运算符栈s1和储存中间结果的栈s2
- 从左至右扫描中缀表达式
- 遇到操作数时,将其压s2
- 遇到运算符时,比较其与s1栈顶运算符的优先级:
- 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈
- 否则,若优先级比栈顶运算符的高,也将运算符压入s1
- 否则,将s1栈顶的运算符弹出并压入到s2中,再次与s1中新的栈顶运算符相比
- 遇到括号时:
- 如果是左括号“(”,则直接压入s1
- 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
- …
- 重复步骤2至5,直到表达式的最右边
- 将s1中剩余的运算符依次弹出并压入s2
- 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
public class Calculator { public static void main(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 = new ListStack1(10); ListStack1 operationStack = new ListStack1(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); } public static void test(String expression, ListStack1 numStack, ListStack1 operationStack) { // 用于扫描 int index = 0; // 将每次扫描得到的char保存到ch char ch = ' '; // 开始while循环的扫描expression while (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 = %dn", expression, res); } public static char getCharByIndex(String expression, int index) { return expression.charAt(index); } public static int numSolve1(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; } public static void operationSolve1(char ch, ListStack1 numStack, ListStack1 operationStack) { // 判断当前符号栈是否具有操作符 if (!operationStack.isEmpty()) { operationSolve2(ch, numStack, operationStack); return; } else { operationStack.push(ch); return; } } public static void operationSolve2(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; } } public static void operationSolve3(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; } public static int priority(char operation) { if (operation == '*' || operation == '/') { return 1; } else if (operation == '+' || operation == '-') { return 0; } else { // 假设目前的表达式只有 + - * / return -1; } } public static boolean isOperation(char val) { return val == '+' || val == '-' || val =='*' || val == '/'; } public static int cal(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; } } class Node1{ Object element; Node1 next; public Node1(Object element) { this(element, null); } public Node1(Object element, Node1 n) { this.element = element; next = n; } public Object getElement() { return element; } public void setElement(Object element) { this.element = element; } public Node1 getNext() { return next; } public void setNext(Node1 next) { this.next = next; } } class ListStack1 { Node1 header; int elementCount; int size; public ListStack1() { header = null; elementCount = 0; size = 0; } public ListStack1(int size) { header = null; elementCount = 0; this.size = size; } public void setSize(int size) { this.size = size; } public void setHeader(Node1 header) { this.header = header; } public int getSize() { return size; } public int getElementCount() { return elementCount; } public boolean isEmpty() { if (elementCount == 0) { return true; } return false; } public boolean isFull() { if (elementCount == size) { return true; } return false; } public void push(Object value) { if (this.isFull()) { throw new RuntimeException("Stack is Full"); } header = new Node1(value, header); elementCount++; } public Object pop() { if (this.isEmpty()) { throw new RuntimeException("Stack is empty"); } Object obj = header.getElement(); header = header.getNext(); elementCount--; return obj; } public Object peek() { if (this.isEmpty()) { throw new RuntimeException("Stack is empty"); } return header.getElement(); } }042 完整版逆波兰计算器
完整版的逆波兰计算器,功能包括如下:
- 支持 + - * / ( )
- 多位数,支持小数
- 兼容处理, 过滤任何空白字符,包括空格、制表符、换页符
package com.atguigu.reversepolishcal; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Stack; import java.util.regex.Pattern; public class ReversePolishMultiCalc { static final String SYMBOL = "\+|-|\*|/|\(|\)"; static final String LEFT = "("; static final String RIGHT = ")"; static final String ADD = "+"; static final String MINUS = "-"; static final String TIMES = "*"; static final String DIVISION = "/"; static final int LEVEL_01 = 1; static final int LEVEL_02 = 2; static final int LEVEL_HIGH = Integer.MAX_VALUE; static Stackstack = new Stack<>(); static List data = Collections.synchronizedList(new ArrayList ()); public static String replaceAllBlank(String s) { // \s+ 匹配任何空白字符,包括空格、制表符、换页符等等, 等价于[ fnrtv] return s.replaceAll("\s+", ""); } public static boolean isNumber(String s) { Pattern pattern = Pattern.compile("^[-\+]?[.\d]*$"); return pattern.matcher(s).matches(); } public static boolean isSymbol(String s) { return s.matches(SYMBOL); } public static int calcLevel(String s) { if ("+".equals(s) || "-".equals(s)) { return LEVEL_01; } else if ("*".equals(s) || "/".equals(s)) { return LEVEL_02; } return LEVEL_HIGH; } public static List doMatch(String s) throws Exception { if (s == null || "".equals(s.trim())) throw new RuntimeException("data is empty"); if (!isNumber(s.charAt(0) + "")) throw new RuntimeException("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); } else if (!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); } else if (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; // 前一个运算符的位置 } else if (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; } throw new RuntimeException("data not match number"); } } // 如果栈里还有元素,此时元素需要依次出栈入列,可以想象栈里剩下栈顶为/,栈底为+,应该依次出栈入列,可以直接翻转整个stack 添加到队列 Collections.reverse(stack); data.addAll(new ArrayList<>(stack)); System.out.println(data); return data; } public static Double doCalc(List list) { Double d = 0d; if (list == null || list.isEmpty()) { return null; } if (list.size() == 1) { System.out.println(list); d = Double.valueOf(list.get(0)); return d; } ArrayList list1 = new ArrayList<>(); 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; } public static Double doTheMath(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; } public static void main(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
觉得文章写的不错的亲亲们,点赞评论走一波,爱你们哦!綾