大连网站建设方案咨询,下沙做网站的,黄山旅游景点,wordpress 音乐主题模板下载#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 中缀表达式转后缀说明 1.1 实现中缀表达式转后缀思路 2.0 逆波兰表达式求值 2.1 实现逆波兰表达式求值思路 3.0 有效的括号 3.1 实现有效的括号思路 4.0 栈的压… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 中缀表达式转后缀说明 1.1 实现中缀表达式转后缀思路 2.0 逆波兰表达式求值 2.1 实现逆波兰表达式求值思路 3.0 有效的括号 3.1 实现有效的括号思路 4.0 栈的压入、弹出序列 4.1 实现栈的压入、弹出序列思路 5.0 最小栈 5.1 实现最小栈思路 1.0 中缀表达式转后缀说明 中缀表达式转后缀表达式是一种常见的算术表达式转换方法它将中缀表达式即常见的人类习惯的表达方式例如3 4 * 2转换为后缀表达式也称为逆波兰表达式例如 3 4 2 * 。中缀表达式转后缀表达式的转换过程通常使用栈来实现。 1.1 实现中缀表达式转后缀思路 1.1.1 思路具体为首先先来讨论优先级问题分两种情况。 情况一不带括号对于 - * / 这个四种运算符来定义优先级大小 - 优先级大小可以设置为 1 * / 优先级大小可以设置为 2 。 情况二带括号对于 ( 来说将其优先级设置为 0 为最小的优先级。 再来讨论代码实现的流程对于运算符或者括号来说将其放到栈中暂时存储对于数字 0 ~ 9 来说将其拼接到可变字符串中。 1.1.2 接下来循环遍历字符串 (1) 遇到非运算符直接拼串 (2) 遇到 - * / - 它的优先级比栈顶运算符高入栈如栈中是 当前是 * - 否则把栈里面的优先级 它的都出栈它再进栈如栈中是 * 当前是 - (3) 遍历完成栈里面剩余运算符依次出栈拼接到字符串中 (4) 带() - 遇到左括号直接入栈左括号优先级设置为 0 。 - 遇到右括号就把栈里面到左括号为止的所有运算符都出栈
代码如下 import java.util.Stack;public class TurnToSuffix {public static void main(String[] args) {String s (ab)*c;System.out.println(turnSuffix(s));String s1 (ab*c-d)*e;System.out.println(turnSuffix(s1));String s2 a*(bc);System.out.println(turnSuffix(s2));}public static String turnSuffix(String s) {if (s.length() 0) {return null;}StringBuilder str new StringBuilder();StackCharacter stack new Stack();for (int i 0; i s.length(); i) {char ch s.charAt(i);switch (ch) {case ( - {//如果是有括号直接进栈stack.push(ch);}case , -,*,/ - {//比较优先级进栈的优先级高不需要弹出进栈的优先级底或者同一级别需要弹出。while ( !stack.isEmpty() priority(ch) priority(stack.peek())) {str.append(stack.pop());}stack.push(ch);}case ) - {while ( !stack.isEmpty() stack.peek() ! () {str.append(stack.pop());}stack.pop();}default - {str.append(ch);}}}int num stack.size();for (int j 0; j num; j) {str.append(stack.pop());}return str.toString();}public static int priority(char f) {if (f () {return 0;} else if (f || f -) {return 1;}else if (f * || f / ) {return 2;}return -1;}
} 2.0 逆波兰表达式求值 逆波兰表达式也称为后缀表达式是一种不需要括号来表示运算顺序的算术表达式。它的计算方式是从左到右扫描表达式遇到操作数就将其压入栈中遇到操作符就从栈中弹出相应数量的操作数进行运算并将结果再次压入栈中。最终栈中的唯一元素就是表达式的值。 题目 给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意 有效的算符为 、-、* 和 / 。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。 示例 1 输入tokens [2,1,,3,*]
输出9
解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 92.1 实现逆波兰表达式求值思路 思路具体为遍历字符串数组将遍历遇到的非运算符都要存放在栈中遇到运算符需要将栈中的数据弹出栈第一个弹出的数据称为右操作数第二个弹出来的数据称为左操作数。接着对应相应的运算符进行对该这两个数据操作得到的计算结果需要重新压入栈中。最后循环结束栈中存放的就是该表达式最终的结果了。
代码如下 class Solution {public static int evalRPN(String[] tokens) {LinkedListInteger stack new LinkedList();for (int i 0; i tokens.length; i) {int a 0;int b 0;switch (tokens[i]) {case :b stack.pop();a stack.pop();stack.push(a b);break;case -:b stack.pop();a stack.pop();stack.push(a - b);break;case *:b stack.pop();a stack.pop();stack.push(a * b);break;case /:b stack.pop();a stack.pop();stack.push(a / b);break;default:stack.push(Integer.parseInt(tokens[i]));break;}}return stack.pop();}
} 需要注意的点是从字符串数组中得到的非运算符是需要将其转换为 int 的包装类型。 3.0 有效的括号 题目 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 1 输入s ()
输出true示例 2 输入s ()[]{}
输出true 该题的 LeetCode 链接20. 有效的括号 3.1 实现有效的括号思路 具体思路为遍历字符串每一次循环得到的字符可以大致分为两种情况 第一种情况遇到的是右括号无论是 ( { [ 的其中一种都需要将其相反的符号压入栈中。如遇到的是 ( 那么需要压入栈的是 ) 。 第二种情况遇到的是左括号无论是 ) } ] 的其中一种先要判断栈中是否为空如果为空直接返回 false 当不为空时若判断栈顶的括号是否跟遇到的左括号相等如果相等将栈顶的括号弹出若不相等直接返回 false 。 最后循环结束了判断栈是否为空如果栈为空了那么说明都一一对称有相应的括号与之匹配如果不为空那么说明不是全部的括号都要相应的括号对应。
代码如下 class Solution {
public static boolean isValid(String s) {if (s.length() 0) {return false;}StackCharacter stack new Stack();for (int i 0; i s.length(); i) {char ch s.charAt(i);switch (ch) {case [ - {stack.push(]);}case { - {stack.push(});}case ( - {stack.push());}default - {if (stack.empty()) {return false;}if (ch ! stack.peek()) {return false;} else if (ch stack.peek()) {stack.pop();}}}}return stack.empty();}
} 4.0 栈的压入、弹出序列 题目 输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。 1. 0pushV.length popV.length 1000 2. -1000pushV[i]1000 3. pushV 的所有数字均不相同 示例1 输入 [1,2,3,4,5],[4,5,3,2,1] 返回值 true 说明 可以通过push(1)push(2)push(3)push(4)pop()push(5)pop()pop()pop()pop()
这样的顺序得到[4,5,3,2,1]这个序列返回true 该题的链接为栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) 4.1 实现栈的压入、弹出序列思路 第一个序列表示栈的压入顺序、第二个序列可能为该栈的弹出顺序 具体思路为遍历第一个序列每一次得到的数值都要跟第二个序列索引从 0 开始到该序列长度 - 1 比较如果从第一个序列得到的数值跟第二个序列的数值不相同时需要将第一序列的数值压入栈中如果从第二个序列得到的数值跟第二个序列的数值相同时需要将第一个序列的数值弹出栈中接着第二个序列跳到下一个数值跟栈中的数值进行比较若相同栈中继续弹出第二个序列继续跳到下一个。若不相同继续遍历第一个序列。 可以简单的理解为每一次循环第一个序列得到数据都要放到栈中接着跟第二个序列的数据进行比较。如果栈顶的数据跟第二个序列的数值相同时需要将其栈顶元素弹出还需要将第二个序列移到下一个元素。接着继续比较直到栈顶元素跟第二个序列的元素不相等是继续遍历第一个序列直到第一个序列遍历完毕。最后判断占是否为空若为空返回 true 若不为空返回 false 。
代码如下 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型一维数组 * param popV int整型一维数组 * return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStackInteger stack new Stack();int j 0;for(int i 0; i pushV.length ; i) {stack.push(pushV[i]);while( !stack.isEmpty() j popV.length stack.peek() popV[j]) {stack.pop();j;}}return stack.isEmpty();}
} 需要注意的是在内层循环时要保证栈中不为空且不能超过第二个序列的长度。 5.0 最小栈 题目 设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。 示例 1: 输入
[MinStack,push,push,push,getMin,pop,top,getMin]
[[],[-2],[0],[-3],[],[],[],[]]输出
[null,null,null,null,-3,null,0,-2]解释
MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); -- 返回 -3.
minStack.pop();
minStack.top(); -- 返回 0.
minStack.getMin(); -- 返回 -2. 该题的 LeetCode 链接为155. 最小栈 5.1 实现最小栈思路 具体思路为因为需要记录栈中的最小元素所以需要用到两个栈对于 stack 栈来说就正常的压栈、出栈、查看栈顶元素等操作即可 压栈处理对于 minStack 栈来说当该栈为空时stack 压栈时minStack 也要压栈相同的元素当 minStack 不为空时satck 压栈时minStack 需要先判断该栈顶元素的值是否大于需要压入栈的元素的值若大于等于则 minStzck 需要将其压入栈若小于则不需要进行任何操作。 出栈处理需要先判断 stack 是否为空栈如果是空栈则不需要进行出栈处理。如果不为空栈stack 需要出栈但是对于 nimStack 不一定需要出栈若 stack 的栈顶与 nimStack 的栈顶元素相同时nimStack 需要出栈。若不相同则不需要出栈。 查看栈顶元素处理直接返回 stack.pop() 即可。 查看最小栈的元素直接返回 minStack.peek() 即可。
代码如下 class MinStack {StackInteger stack;StackInteger minStack ;public MinStack() {stack new Stack();minStack new Stack();}public void push(int val) {stack.push(val);if(minStack.isEmpty()) {minStack.push(val);}else if(minStack.peek() val) {minStack.push(val);}}public void pop() {if(stack.pop().equals(minStack.peek())){minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
} 需要注意的是 stack 与 minStack 的栈顶元素进行比较时需要用 equals() 方法进行比较不然会发生问题。
