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;
}
最后修改:2023 年 05 月 24 日
如果觉得我的文章对你有用,请随意赞赏