关于栈的常见编程题

一、括号匹配

    LeetCode——20.有效的括号

题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

例：

输入："(){}[]" 输出：true

输入："({[]})" 输出：true

输入："(}{)" 输出：false

输入："(){]" 输出：false

思考：

此时我们可以利用栈先入后出的特性，以"({[]})"为例，先在栈中压入"("，后看剩余字符串中的第一个元素是否与栈顶元素相匹配，如果不匹配，则入栈，否则出栈，到下一个字符。

我们也可以进行优化，如上述描述，入栈的一定都是左括号，碰到右括号再去进行匹配，匹配不成功则直接返回false，当字符串走完的时候，如果栈为空，则返回true，否则返回false。

括号匹配

import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
        char[] arr=s.toCharArray();
        Stack<Character> stack=new Stack<>();
        for(char n:arr){
            if(stack.empty()){
                stack.push(n);
                continue;
            }
            char a=stack.peek();
            char b=n;
            if(
                (a=='('&&b==')')||
                (a=='{'&&b=='}')||
                (a=='['&&b==']')
            )
            {
                stack.pop();
            }else{
                stack.push(n);
                if(
                    b==')'||
                    b==']'||
                    b=='}'
                ){
                    break;
                }
            }
        }
        return stack.empty();
    }
}

二、逆波兰表达式求值

LeetCode——150.逆波兰表达式求值

要想做这类题目，首先要知道什么是逆波兰表达式（后缀表达式）。

我们生活中最常见的就是中缀表达式，举一个简单的例子：a+bc+(de+f)*g

而如何将中缀表达式转换成后缀表达式呢？

首先，将中缀表达式用括号分开：( （ a+（bc））+（（（de）+f ）*g) )

然后，将各个表达式中的预算符放到相对应的括号后面：

abc+de*f+g+**

（前缀表达式同理）

前缀：++abc+*defg

那我们如何计算这种后缀表达式呢？

将数字放入栈当中，碰到运算符则弹出栈顶元素，先弹出的放运算符右边，后弹出的放运算符左边，将运算好的结果放回到栈中，重复上述过程知道后缀表达式走完

import java.util.Stack;
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack =new Stack<>();
        for(String n:tokens){
             if(n.equals("*")){
                 int a=stack.pop();
                 int b=stack.pop();
                 stack.push(b*a);
                 continue;
             }else if(n.equals("+")){
                 int a=stack.pop();
                 int b=stack.pop();
                 stack.push(b+a);
                 continue;
             }else if(n.equals("-")){
                 int a=stack.pop();
                 int b=stack.pop();
                 stack.push(b-a);
                 continue;
             }else if(n.equals("/")){
                 int a=stack.pop();
                 int b=stack.pop();
                 stack.push(b/a);
                 continue;
             }
             int m=Integer.valueOf(n);
             stack.push(m);
        }
        return stack.peek();
    }
}

而同理，如果是让我们求前缀表达式的值，我们应从后往前遍历前缀表达式，将数字放入栈中，而碰到运算符，则弹出栈顶元素，注意：先弹出的元素此时应该放运算符的左边，后弹出的元素应该放运算符的右边，重复上述步骤，知道前缀表达式走完。

三、出栈入栈次序匹配

1、选择题之选择哪一种是正确的次序匹配函数

例：1.若进栈顺序为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈顺序为（）

 A、1，4，3，2       B、2，3，4，1    C、3，1，4，2    D、3，4，2，1

答案：C

这类题目较简单，依次去排除就好了。

2、编程题之判断出栈顺序是否存在可能

LeetCode——946.验证栈序列

注意此题目入栈过程中可以出栈！

题目说明：

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

先将pushed数组中的数字依次入栈，如果栈顶元素与出栈数组中的数字匹配，则将栈顶元素出栈，否则入栈，如果当pushed数组遍历完成之后，栈中依旧存在元素，则返回false，否则返回true

import java.util.Stack;
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        int m=popped.length;
        for(int n:pushed){
            stack.push(n);
            while(!stack.empty()&&j<m&&popped[j]==stack.peek()){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}