【代码随想录训练营】【Day11】第五章｜栈与队列｜20. 有效的括号｜1047. 删除字符串中的所有相邻重复项｜150. 逆波兰表达式求值

20. 有效的括号

题目详细：LeetCode.20

由题可知，有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

那么，我们可以利用栈后进先出的特点：

• 当遍历到左括号时，将左括号字符依次进栈
• 当遍历到右括号时，将栈顶的左括号字符出栈
  • 左括号如果与闭括号属于相同类型，则为有效括号，继续遍历下一个字符
  • 左括号如果与闭括号属于不同类型，则为无效括号，栈内剩余的左括号也无法以正确的顺序闭合，返回false
  • 如果栈为空，则说明不存在与之匹配的左括号，返回false
• 当遍历完输入的字符串后，注意需要判断栈是否为空，进而来判断字符串内的括号是否已完全匹配

Java解法（栈）：

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(char a: s.toCharArray()){if(a == '(' || a == '{' || a == '['){stack.push(a);}else if(stack.isEmpty()){return false;}else{char b = stack.pop();// 在ASCII码中，左括号和右括号的差值 <= 2// 所以这里直接用 Math.abs(a-b) 来判断左右括号是否匹配if(Math.abs(a-b) > 2){return false;}}}return stack.isEmpty();}
}

---

1047. 删除字符串中的所有相邻重复项

题目详细：LeetCode.1047

这道题的实现方式不同，但解决思路是殊途同归的，都是利用栈后进先出的存储特点来解题：

• 字符串中的字符依zg次进栈，这样就保证了出栈的字符一定与下一个字符是相邻的
• 那么只需要比较栈顶元素和即将进栈的元素是否重复
  • 如果重复，则弹出栈顶元素
  • 如果不重复，则将遍历到字符进栈
• 最后只需要将栈内的字符重新组成字符串，即为无重复项的字符串。

Java解法（栈）：

class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for(char a : s.toCharArray()){if(stack.isEmpty()){stack.push(a);}else{char b = stack.pop();if(a != b){stack.push(b);stack.push(a);}}}StringBuffer sb = new StringBuffer();while(!stack.isEmpty()){sb.insert(0, stack.pop());}return sb.toString();}
}

无独有偶，我们也可以用同样具备后进先出特点的双向队列来解决这道问题：

Java解法（双向队列）：

class Solution {public String removeDuplicates(String s) {Deque<Character> deque = new LinkedList<>();for(char a : s.toCharArray()){if(deque.isEmpty()){deque.add(a);}else{char b = deque.pollLast();if(a != b){deque.add(b);deque.add(a);}}}StringBuffer sb = new StringBuffer();while(!deque.isEmpty()){sb.append(deque.poll());}return sb.toString();}
}

还有更为效率的方法，就是将字符串转为字符数组后，通过双指针，来模拟栈进栈和压栈时栈顶指针的移动，以及对重复字符的替换的过程，来解决这一问题：

Java解法（双指针/模拟栈）：

class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray();int top = 0;int next = 0;while(next < s.length()){ch[top] = ch[next];if(top > 0 && ch[top] == ch[top - 1]){top--;}else{top++;}next++;}return new String(ch,0,top);}
}

---

150. 逆波兰表达式求值

题目详细：LeetCode.150

波兰表达式，其实就是将表达式用二叉树的形式表示后，中序遍历二叉树得到的序列；而逆波兰表达式，就是后序遍历二叉树得到的序列。

观察逆波兰表达式的数组，可以发现：

• 利用栈先进后出的特点，能够保证两个数值计算的前后顺序
• 当遇到一个算术符号时，则在栈中弹出最近的两个数
• 将这两个数，按照算术符号进行相应的术式计算出结果
• 然后将计算结果再次压入栈中，保证后续数值计算的前后顺序
• 直到表达式遍历完，栈中仅剩的计算结果即为最终结果

Java解法（双指针/模拟栈）：

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> deque = new LinkedList<>();for(String t: tokens){if(t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")){int a = 0, b = 0, c = 0;a = deque.pollLast();b = deque.pollLast();switch(t){case "+":c = b + a;break;case "-":c = b - a;break;case "*":c = b * a;break;case "/":c = b / a;break;}deque.add(c);}else{deque.add(Integer.parseInt(t));}}return deque.poll();}
}