Interview high-frequency test questions solution - stack push and pop sequence, effective parentheses, reverse Polish expression evaluation

目录

热身：

JZ31栈的压入、弹出序列

逆波兰表达式求值

有效的括号

---

热身：

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

        分析：There is an implicit condition here,压栈序列1,2,3,4,push the stack at that time,You can then pop out of the stack,简单来讲,让1进栈时,You can then1弹出栈,Push back on the stack;

        如此分析,只有BOption is eligible：1进栈,2进栈,与BOption first pop sequence match,弹出2,Look at the push sequence again：1with the popup sequence3不匹配,Continue to compare the next element of the pushed sequence,如此往复,可得出答案.

---

JZ31栈的压入、弹出序列

 思路：

1. 创建一个栈stack
2. The push sequence is pushed first and then compared with the pop sequence
3. Pop up if equal

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;//计数：Increment by one if it matches the pushed data
        for(int i = 0; i < pushA.length; i++){
            if(pushA[i] == popA[count]){
                //先压栈,再判断
                stack.push(pushA[i]);
                while(stack.peek() == popA[count]){
                    stack.pop();
                    count++;
                    //popAThe instructions are correct after traversing
                    if(count == pushA.length){
                        return true;
                    }
                    /**
                    *弹出栈后,There may not be a single element left,这时再到while里判断,
                    *It is possible to dereference a null pointer
                    */
                    if(stack.empty()){
                        break;
                    }
                }
            }
            else{
                stack.push(pushA[i]);
            }
        }
        return false;
    }
}

---

逆波兰表达式求值

The blogger has sorted out the blog,快去看看吧~

http://t.csdn.cn/adU0q

---

有效的括号

It is also in the understanding of the stack,Frequently asked questions

      思路：

                1.创建一个栈

                2.Traverse the given array in the large direction

                3.The small direction is compared to see if it matches

      注意：Mismatch is divided into the following situations

                a.左右括号不匹配

                b.右括号多：当前下标是右括号,但栈为空

                c.左括号多：The string array traversal is complete,But the stack is still not empty

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '{' || ch == '['){
                stack.push(ch);
            }
            else{
                //说明ch是右括号
                if(stack.empty()){
                    //右括号多
                    return false;
                }
                char tmp = stack.peek();
                if(tmp == '(' && ch == ')' || 
                   tmp == '{' && ch == '}' || 
                   tmp == '[' && ch == ']'){
                       //The current parenthesis matches
                       stack.pop();
                }
                else{
                    //左右括号不匹配
                    return false;
                }
            }
        }
        //判断是否为空
       if(stack.empty()){
            return true;
        }
        else{
            //左括号多
            return false;
        }
    }
}