数据结构（十二）——栈（下）（面试题）
一、有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。示例 1：
输入：s = "()"
输出：true
示例 2：输入：s = "()[]{}"
输出：true
示例 3：输入：s = "(]"
输出：false
解题思路：本题我们可以利用栈来解决，首先我们遍历字符串，把我们遇到的左括号先进栈，遇到右括号不进栈，这个时候先判断栈是否为空，若为空，那么就是右括号多了，直接返回false；否则这时栈顶元素弹出，看这两个括号是否匹配，匹配循环继续，直到最后栈为空，不匹配，直接返回false。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack();
//1.遍历字符串
for(int i=0;i<s.length();i++){
char ch = s.charAt(i);
//2.判断是不是左括号
if(ch=='('|| ch=='['|| ch=='{'){
stack.push(ch);
}
else{
//3.遇到右括号
if(stack.empty()){
return false;
}
char ch2 = stack.peek();
if(ch2 == '[' &&ch == ']'||ch2 == '(' &&ch == ')'||ch2 == '{' &&ch == '}'){
//出去匹配这个左括号
stack.pop();
}
else{
return false;
}
}
}
//当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成
if(!stack.empty()){
return false;
}
return true;
}
}
二、逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
解题思路：
逆波兰表达式其实就是中缀转后缀，我们平时见得1+2-3/4*5，都是中缀，因为运算符在操作数的中间，那么后缀就是运算符在操作数的后面，转为中缀就是两个操作数把后面的运算符放在中间然后加上括号即可。1、我们可以用栈来解决这个问题，遍历给定的字符串，遇到数字就进栈，遇到操作数，出栈两个元素，第一个出栈的元素为运算符的右操作数，第二个出栈的操作数为运算符的左操作数，最后将求得的结果入栈便可。
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String s:tokens){
if(!isOperations(s)){
stack.push(Integer.parseInt(s));
}else{
int num2 = stack.pop();
int num1 = stack.pop();
switch(s){
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();
}
public boolean isOperations(String s){
if(s.equals("+")|| s.equals("-")|| s.equals("*")||s.equals("/")){
return true;
}
return false;
}
}
三、出栈入栈次序匹配
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
示例1
输入：
[1,2,3,4,5],[4,5,3,2,1]
返回值：
true
说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true 。
示例2
输入：
[1,2,3,4,5],[4,3,5,1,2]
返回值：
false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false 。
解题思路：
在我的上篇博客就提到过出栈入栈次序匹配问题，那是个选择题，非常简单，那么这题是一道编程题，我们可以这样来求解，因为题目给了两个序列，我们首先遍历第一个序列，让其元素进栈，在这个循环中如果栈顶元素等于给定序列，那么栈顶元素出栈，j++，函数返回值直接判断栈是否为空，为空说明我们的次序是匹配的，不为空，说明这个序列不合法！
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA, int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (j < popA.length && !stack.empty()
&& stack.peek().equals(popA[j])) {
//用equals是因为Integer的范围是-128~127 如果超过这个范围肯定会报错 系统给的测试用例应该没有超过这个范围 所以测试可以通过
stack.pop();
j++;
}
}
return stack.empty();
}
}