1.有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 1.左括号必须用相同类型的右括号闭合。
- 2.左括号必须以正确的顺序闭合。
- 3.每个右括号都有一个对应的相同类型的左括号。
- 题解:
思路:
1.若字符串长度是0或1都不可能是合法括号,直接返回false;
2.字符串修改成字符,对字符一个一个判断,若字符是左括号,就把他放入栈中,若字符是右括号,就在栈顶出一个元素,两个元素合并一起,判断看是否是有效括号。
class Solution { public boolean isValid(String s) { //一个或者是空,都是false if(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.逆波兰表达式求值
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意:
- 有效的算符为
'+'
、'-'
、'*'
和'/'
。 - 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
题解:
思路:
1.遇见数字就入栈;
2.遇见运算符就出栈,出两个数,再将运算后的结果入栈;
3.最终栈中的元素就是计算结果。
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(); } }