有效的括号
题目链接
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
思路
考虑三种情况
1、左括号多
2、右括号多
3、括号不多不少但不匹配
public boolean isValid(String s) {
Stack<Character> stack = new Stack();
int i = 0;
while(i < s.length()) {
if(s.charAt(i) == '(') {
stack.push(')');
} else if(s.charAt(i) == '{') {
stack.push('}');
} else if(s.charAt(i) == '[') {
stack.push(']');
} else if(stack.isEmpty() || stack.pop() != s.charAt(i)) {
return false;
}
i++;
}
return stack.isEmpty();
}
删除字符串中的所有相邻重复项
题目链接
思路
和上一题差不多，比较简单
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack();
int i = 0;
while(i < s.length()) {
if(stack.isEmpty() || stack.peek() != s.charAt(i)) {
stack.push(s.charAt(i));
} else {
stack.pop();
}
i++;
}
StringBuilder stringBuilder = new StringBuilder();
while(!stack.isEmpty()) {
stringBuilder.append(stack.pop());
}
return stringBuilder.reverse().toString();
}
逆波兰表达式求值
题目链接
思路
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String str : tokens) {
if(str.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if(str.equals("-")) {
stack.push(-stack.pop() + stack.pop());
} else if (str.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if(str.equals("/")) {
int t1 = stack.pop();
int t2 = stack.pop();
stack.push(t2/t1);
} else {
stack.push(Integer.valueOf(str));
}
}
return stack.pop();
}