C++栈应用——括号匹配

说明

学过数据结构的大多都做过这道题，给定一串表达式，匹配前后对应的括号。

实际上思路很简单，由于栈是FILO（先进后出）的，字符串读取顺序从左到右，左括号一定在右括号左面，利用几点，我们在读取字符串的时候将左括号（或其位置）入栈，读到右括号就出栈即可。

代码

这段代码利用栈，将左括号的位置存入栈中，读到右括号，就出栈获取对应左括号位置。一个右括号一定对应一个唯一的左括号，所以我将他们的位置关系放到了map中，这样如果有输出括号位置的要求直接从map中获取。

#include <bits/stdc++.h>

using namespace std;

map<int,int> func(string s){
    map<int,int> res;
    stack<int> st;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
            st.push(i);
        }else{
            if(s[i]==')' || s[i]==']' || s[i]=='}'){
                int temp = st.top();
                res[i] = temp;
                st.pop();
            }
        }
    }
    return res;
}


int main(){
    
    string s;
    cin >> s;
    auto res = func(s);
    for(auto i = res.begin();i!=res.end();i++){
        cout << s[i->second] << ":" << i->second << " <-> " << s[i->first] << ":" << i->first << endl;
    }
    
    return 0;
}