栈与队列part02
今日内容:
● 20. 有效的括号
● 1047. 删除字符串中的所有相邻重复项
● 150. 逆波兰表达式求值
1.20. 有效的括号
class Solution {
public boolean isValid(String s) {
//思路:我们可以进行遍历现在的字符串
//如果遍历到是左相关的,我们就将对应的右括号存储到栈中,然后继续遍历
//党遍历到右括号就比较下栈里的括号是否一样,如果一样则证明找到一对,进行出去栈顶元素
//字符串继续向下遍历,直到全部遍历完
/*会遇到的情况:
左括号必须用相同类型的右括号闭合。(没有找到右边的就抵消不了,栈中会剩下元素)
左括号必须以正确的顺序闭合。(抵消不了)
每个右括号都有一个对应的相同类型的左括号。(栈中没有元素了,但是字符串还没有遍历完)
*/
//定义一个栈
Stack<Character> stack=new Stack<>();
//遍历字符串
for(int i=0;i<s.length();i++){
switch(s.charAt(i)){
case '(':{
stack.push(')');
break;
}
case '{':{
stack.push('}');
break;
}
case '[':{
stack.push(']');
break;
}
case ')':{
//如果栈顶是')'的话,就进行出栈
//如果没有')'的话,就证明是多出来的右括号,(没有相同类型的左括号)
//获得栈顶元素peek,但不移除
//char value=stack.peek();
if(!stack.isEmpty()&&stack.peek()==')'){
//字符串还没遍历完的情况,栈就为空,那么此时就是右括号多余出来了,没能进行匹配
//栈顶元素和遍历到的元素不一样,那么就是左右不匹配
//那剩下一种情况左括号多余呢,那就是字符串全部都遍历完了,但是栈中还有元素,就证明是左括号多余
//进行出栈
stack.pop();
}else{
//不匹配,那么可以直接证明字符串不匹配了
return false;
}
break;
}
case '}':{
//char value=stack.peek();
if(!stack.isEmpty()&&stack.peek()=='}'){
//进行出栈
stack.pop();
}else{
//不匹配,那么可以直接证明字符串不匹配了
return false;
}
break;
}
case ']':{
//char value=stack.peek();
if(!stack.isEmpty()&&stack.peek()==']'){
//进行出栈
stack.pop();
}else{
//不匹配,那么可以直接证明字符串不匹配了
return false;
}
break;
}
}
}
//那剩下一种情况左括号多余呢,那就是字符串全部都遍历完了,但是栈中还有元素,就证明是左括号多余stack.isEmpty()=false
//当字符串遍历完了,栈中也没有元素了,就证明已经成对存在stack.isEmpty()=true
return stack.isEmpty();
}
}
2.1047. 删除字符串中的所有相邻重复项
class Solution {
public String removeDuplicates(String s) {
//思路:我们遍历字符串,遍历到一个字母,我们就将一模一样的它存进到栈中
//然后遍历下一个跟栈顶元素对比,如果一样就进行出栈,然后字符串往下遍历
//如果跟栈顶元素不一样,那么就继续存进栈中
//组后要返回的字符串是出栈之后的倒序
//定义一个字符串
String result="";
//定义一个栈
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
//空栈不能取栈顶元素,会报空指针异常
//无论怎样,先将字符串第一个元素存进栈中
//stack.push(s.charAt(0));
//不行,因为这样子第一个元素会被抵消
// if(stack.isEmpty()||stack.peek()!=s.charAt(i)){
// stack.push(s.charAt(i));
// }else{
// stack.pop();
// }
if(stack.isEmpty()){
stack.push(s.charAt(i));
}else{
//栈不为空的情况
//遍历到的元素不等于栈顶元素
if(s.charAt(i)!=stack.peek()){
//那么就将该值存进栈中
stack.push(s.charAt(i));
}else{
//如果遍历到的元素跟栈顶元素一样的话就进行抵消,栈顶元素出栈
stack.pop();
}
}
}
//全部都遍历完了
//最终返回的是一个字符串类型
//将栈顶元素存进字符串中再倒序
String value="";
while(!stack.isEmpty()){
//做了大半天,原来是这里的while写成if了
value+=stack.peek();
stack.pop();
}
// return new String(result).reverse();
for(int i=value.length()-1;i>=0;i--){
result+=value.charAt(i);
}
return result;
}
}
3.150. 逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
//我们平常熟悉的算数表达式比如说(1+2)*(3+4),也叫中缀表达式
//逆波兰表达式,也叫后缀表达式,就是一颗二叉数的后序
//二叉树进行左右中排序就变成了后缀表达式
//(1+2)*(3+4)二叉树表达成如下
/**
第一层: *
第二层:+ +
第三层:1 2 3 4
按照左右中就是: 12+34+*
12+34+*这个就是逆波兰表达式,也就是后缀表达式
*/
//解决思路:进行遍历字符串,遇到数字就存进栈中,遇到算符就从栈中弹出两个数字进行计算
//计算完再将这个结果入栈
//定义一个栈
Stack<Integer> stack=new Stack<>();
//定义一个结果
//int stackresult=0;
for(int i=0;i<tokens.length;i++){
leetcode 内置jdk的问题,不能使用==判断字符串是否相等
//判断字符串相等得用 字符串.equals(字符串)
//正难则反
switch(tokens[i]){
case "+":{
//取出栈中两个元素,进行计算
//int result=parseInt(stack.pop())+parseInt(stack.pop());
//把结果存进栈中
//stack.push(result);
int temp1=stack.pop();//隐式转换
int temp2=stack.pop();
stack.push(temp1+temp2);//直接就是返回整形的吗???
break;
}
case "-":{
//取出栈中两个元素,进行计算
//int result=parseInt(stack.pop())-parseInt(stack.pop());
//把结果存进栈中
//stack.push(result);
int temp1=stack.pop();//隐式转换
int temp2=stack.pop();
stack.push(-temp1+temp2);//直接就是返回整形的吗???
//为什么是-temp1+temp2,不然实例过不了
break;
}
case "*":{
//取出栈中两个元素,进行计算
//int result=parseInt(stack.pop())*parseInt(stack.pop());
//把结果存进栈中
//stack.push(result);
int temp1=stack.pop();//隐式转换
int temp2=stack.pop();
stack.push(temp1*temp2);//直接就是返回整形的吗???
break;
}
case "/":{
//取出栈中两个元素,进行计算
//int result=parseInt(stack.pop())/parseInt(stack.pop());
//把结果存进栈中
//stack.push(result);
int temp1=stack.pop();//隐式转换
int temp2=stack.pop();
stack.push(temp2/temp1);//直接就是返回整形的吗???
//为什么是temp2/temp1,不然实例过不了
break;
}
//不然就证明是数字
//数字就存进栈中
default:{
//跟所有的case都不匹配才会执行
//stack.push((int)tokens[i]);
stack.push(Integer.valueOf(tokens[i]));
break;
}
}
}
//所有都遍历完了
//此时的结果就是栈中所存的值,转为int类型返回
//stackresult=(int)stack.peek();
return stack.pop();
}
}