括号匹配问题

题目

分析

开一个栈来记录左括号位置，而不是记录左括号。扫描原字符串，遇到右括号，查看栈是否空，若不空则匹配，若空则不匹配。扫描结束后，查看栈是否为空，若不空，则栈中存放的是未匹配的的左括号。

代码

#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main(){
    string s;
    while(cin>>s){
        stack<int>stk; //保存括号在原字符串中的下标
        string res(s.size(),' ');
        for(int i = 0;i<s.size();i++){
            if(s[i] == '('){
                stk.push(i);
            }else if(s[i] == ')'){
                if(!stk.empty())
                    stk.pop();
                else 
                    res[i] = '?';
            }
        }
        while(!stk.empty()){
            res[stk.top()] = '$';
            stk.pop();
        }
        cout<<s<<endl;
        cout<<res<<endl;
    }
}