栈总结

栈是比较常见的数据结构，简单来说就是“先进后出”，常用的方法有push(),pop(),top()，定义的方式是stack<int> s。栈常见的题型有两种，一种是括号匹配，另一种则是表达式求解。

1. 括号匹配：如果是左括号则进栈，如果是右括号则要先判断栈内有没有元素，再与栈顶元素做匹配。如果有要求括号优先级，则用一个map记录优先级，每次进栈先判断优先级比里面元素小才进栈。

#include <iostream>
#include <stack>
#include <map>
using namespace std;
int main(){
    stack<char> st;
    map<char,int> map1;
    map1['{'] = 4;
    map1['['] = 3;
    map1['('] = 2;
    map1['<'] = 1;
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){
        int flag = 0;
        string buf;
        cin>>buf;
        int len = buf.length();
        for(int j = 0;j < len;j++){
            if(!st.empty()) {
                if (map1[st.top()] >= map1[buf[j]]) {
                    if ((buf[j] == ']' && st.top() == '[') || (buf[j] == '>' && st.top() == '<') ||
                        (buf[j] == ')' && st.top() == '(') || (buf[j] == '}' && st.top() == '{'))
                        st.pop();
                    else
                        st.push(buf[j]);
                }else{
                    cout<<"NO"<<endl;
                    flag = 1;
                    break;
                }
            }
            else
                st.push(buf[j]);
        }
        if(!flag){
            if(!st.empty())
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
        }
        while (!st.empty())
            st.pop();
    }
}

2.表达式求解：初始化两个栈，一个是运算符栈一个是数字栈，定义好运算符的优先级（通过二维数组），如果是数字则入数字栈，如果是运算符则比较优先级，如果来的运算符优先级比栈顶运算符优先级更高则如栈，如果更低则从数字栈弹出两个数字进行相关运算。