Find the order number of parenthesis pairs in a given string

Question

Print out the order number of opening and closing parenthesis in a string For example "((())(()))" the output should be "1 2 3 3 2 4 5 5 4 1"

means that "1st openning parenthesis, 2nd openning, 3rd openning, 3rd openning's closing parenthesis, 2nd openning's closing, 4th openning,..." and so on

I've tried using stack but have no idea what to do after the first closing parenthesis i hit

This is what i have so far

#include <bits/stdc++.h>
using namespace std;

void check(string s){
    stack<char> a;
    char ch[s.length()];
    int done = 0;
    for (char tmp : ch){
        if (tmp == '('){
            a.push(tmp);
            cout<<a.size() + done<<" ";
        }
        if(tmp == ')'){
            a.pop();
            done++;
            cout<<a.size() + done<<" ";
        }
    }
}

main(){
    string s;
    getline(cin, s);
    check(s);
}

Answer 1

For what you want to achieve this code will do:

void check(const std::string & string_){
    std::vector<bool> pars;
    std::string::size_type iterator = 0;
    for(const auto character : string_){
        if (character == '('){
            pars.push_back(true);
            std::cout << (iterator = pars.size()) << "  ";
        }
        else if (character == ')'){
            while(!pars[--iterator]);
            pars[iterator] = false;
            std::cout << iterator + 1 << "  ";
        }
    }
}

The key is not to discard any element until the end! But just to mark them closed if a parenthesis get closed. And not to mention, to add a new element when a parenthesis gets open. The index in case of opening will be the number of the elements and when closing index will jump back to the last (still) open element!

For check("((())(()))"); result will be 1 2 3 3 2 4 5 5 4 1

For check("((())(()))()()"); result will be 1 2 3 3 2 4 5 5 4 1 6 6 7 7 (BTW is this behaviour OK?)

However for check("))(()))()()"); program will crash obviously because of the invalid index for the vector!

I suppose it can be fixed but I am wondering what would be the meaning of that. Are negative numbers allowed?

Still I recommend you to use some form of the following based on its clear logic :

#include <string>
void check(const std::string & string_){
    int counter = 0;
    for(const auto character : string_){
        if (character == '(') std::cout << ++counter;
        else if (character == ')') std::cout << --counter;
    }
    std::cout << std::endl;
}

By calling it check("((())(()))"); result will be 1232123210

Good luck!