标签：遍历 匹配 括号 字符串 求值 return stack 表达式
一、有效的括号
20. 有效的括号
1.方法概述
- 使用栈来解决,遍历该字符串，如果是左括号，就将其对应的右括号存进栈，然后和栈顶元素进行匹配，如果匹配为相同的字符，栈顶的元素则弹出，如果不匹配则不满足题意，如果栈都为空了，字符还没匹配完，则说明右括号多了不匹配。否则就是字符串遍历完之后，栈也为空了，说明匹配成功。
2.具体实现
Java实现
点击查看代码
class Solution {
public boolean isValid(String s) {
if(s.length() == 0 || s == null) return true;
if(s.length() % 2 != 0) return false;
Stack<Character> stack = new Stack<>();
for(int i = 0;i < s.length();i++){
char ch = s.charAt(i);
if(ch == '('){
stack.push(')');
}else if(ch == '['){
stack.push(']');
}else if(ch == '{'){
stack.push('}');
}else if(stack.isEmpty() || stack.peek() != ch){
return false;
}else{
stack.pop();
}
}
return stack.isEmpty();
}
}
3.要点总结
- 由于栈结构的特殊性，非常适合做对称匹配类的题目。如果要匹配栈顶元素一定是和遍历完左括号后匹配的。
- 第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false。第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false。第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false。第四种情况：就是完全匹配的情况了。那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。分析完之后，代码其实就比较好写了，但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
二、删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项
1.方法概述
- 用双端队列来模拟栈，就是存放遍历过的元素，当遍历当前的这个元素的时候，去“栈”里看一下我们是不是遍历过相同数值的相邻元素。然后再去做对应的消除操作。从”栈“中弹出剩余元素，此时是字符串，因为从“栈”里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。
2.具体实现
Java实现
点击查看代码
class Solution {
public String removeDuplicates(String s) {
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for(int i = 0;i<s.length();i++){
ch = s.charAt(i);
if(deque.isEmpty() || deque.peek() != ch){
deque.push(ch);
}else{
deque.pop();
}
}
String str = "";
while(!deque.isEmpty()){
str = deque.pop()+str;
}
return str;
}
}
3.要点总结
- 该题要求的是字符串顺序，如果str += deque.pop()，则是逆序的，需要注意。
三、 逆波兰表达式求值
150. 逆波兰表达式求值
1.方法概述
- 当都是数字的时候进栈，当遇到运算符时，弹出栈中的两个元素，第一个弹出的元素放在运算符的右侧，第二个弹出的元素放在运算符的左侧，然后进行运算，运算后继续进栈，栈为空时结束。
2.具体实现
Java实现
点击查看代码
import java.util.*;
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
Integer tmp1,tmp2;
for(int i = 0;i<tokens.length;i++){
String str = tokens[i];
switch(str){
case "+":
tmp2 = stack.pop();
tmp1 = stack.pop();
stack.push(tmp1+tmp2);
break;
case "-":
tmp2 = stack.pop();
tmp1 = stack.pop();
stack.push(tmp1-tmp2);
break;
case "*":
tmp2 = stack.pop();
tmp1 = stack.pop();
stack.push(tmp1*tmp2);
break;
case "/":
tmp2 = stack.pop();
tmp1 = stack.pop();
stack.push(tmp1/tmp2);
break;
default:
stack.push(Integer.valueOf(str));
}
}
return stack.pop();
}
}
3.要点总结
- 逆波兰式（Reverse Polish Notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。
标签：遍历,
匹配,
括号,
字符串,
求值,
return,
stack,
表达式
From： https://www.cnblogs.com/neverlate/p/17141981.html
