目录
1.有效的括号
2.逆波兰表达式求值
1.有效的括号
点击进入该题 https://leetcode.cn/problems/valid-parentheses/description/
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
题解:
思路:
- 若字符串长度是0或1都不可能是合法括号,直接返回false;
- 字符串修改成字符,对字符一个一个判断,若字符是左括号,就把他放入栈中,若字符是右括号,就在栈顶出一个元素,两个元素合并一起,判断看是否是有效括号。
class Solution {public boolean isValid(String s) {//一个或者是空,都是falseif(s.length()==1||s.length()==0) {return false;}Stack<Character> Stack1=new Stack<>();//判断是左括号还是右括号for(int i=0;i<s.length();i++) {char ch=s.charAt(i);if(s.charAt(i)=='{'||s.charAt(i)=='('||s.charAt(i)=='[') {Stack1.push(s.charAt(i));}if(s.charAt(i)=='}'||s.charAt(i)==')'||s.charAt(i)==']') {StringBuffer sb=new StringBuffer();//拿之前看栈是否为空if(Stack1.empty()) {return false;}sb.append(Stack1.pop());sb.append(ch);String str=sb.toString();//判断左右括号是否匹配if(str.equals("{}")||str.equals("[]")||str.equals("()")) {continue;}else {return false;}}}//判断栈是否出完if(!Stack1.empty()) {return false;}return true;}
}
2.逆波兰表达式求值
点击进入该题https://leetcode.cn/problems/evaluate-reverse-polish-notation/
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
- 有效的算符为
'+'
、'-'
、'*'
和'/'
。 - 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
题解:
思路:
- 遇见数字就入栈;
- 遇见运算符就出栈,出两个数,再将运算后的结果入栈;
- 最终栈中的元素就是计算结果。
class Solution {public int evalRPN(String[] tokens) {Stack<Integer>Stack=new Stack<>();for(int i=0;i<tokens.length;i++) {//判断是否是运算符号if(!tokens[i].equals("+")&&!tokens[i].equals("-")&&!tokens[i].equals("*")&&!tokens[i].equals("/")) {Stack.push(Integer.parseInt(tokens[i]));}else {int num2=Stack.pop();int num1=Stack.pop();switch (tokens[i]) {case "/":Stack.push(num1/num2);break;case "+":Stack.push(num1+num2);break;case "-":Stack.push(num1-num2);break;case "*":Stack.push(num1*num2);break;}}}return Stack.pop();}
}