Algorithms-UCSanDiego

Data Structures and Algorithms by UCSanDiego

View project on GitHub

1. Bracket Match

https://en.wikipedia.org/wiki/Brace_matching

Problem

Solutions

CPP

    #include <iostream>
    #include <vector>
    #include <string>

    using namespace std;

    class Solution {
    public:
        using Stack = vector< pair< char,int > >;
        int match( const string& A, Stack stack={}, string open="[{(", string close="]})" ){
            auto i{ 0 };
            for( auto c: A ){
                ++i; // 1-based indexing
                auto open_index = open.find( c ),
                     close_index = close.find( c );
                if( open_index == string::npos && close_index == string::npos )
                    continue;
                if( open_index != string::npos ){
                    stack.push_back({ close[ open_index ], i });
                } else {
                    if( stack.empty() )
                        return i;
                    auto target = stack.back().first;
                    auto match_index = close.find( target );
                    if( c != close[ match_index ] )
                        return i;
                    stack.pop_back();
                }
            }
            return( stack.empty() )? 0 : stack[ 0 ].second;
        }
    };

    int main() {
        string input;
        getline( cin, input );
        Solution solution;
        auto ans = solution.match( input );
        if( ans == 0 )
            cout << "Success" << endl;
        else
            cout << ans << endl;
        return 0;
    }

Python3

    from typing import List, Tuple

    Pair = Tuple[ str,int ]
    Stack = List[ Pair ]

    class Solution:
        def match( self, A: str, stack: Stack=[], open: str="[{(", close: str="]})" ) -> int:
            i = 0
            for c in A:
                i += 1 # 1-based indexing
                open_index = open.find( c )
                close_index = close.find( c )
                if open_index == -1 and close_index == -1:
                    continue
                if open_index != -1:
                    stack.append(( close[ open_index ], i ))
                else:
                    if not stack:
                        return i
                    target, _ = stack[ -1 ]
                    match_index = close.find( target )
                    if c != close[ match_index ]:
                        return i
                    stack.pop()
            return 0 if not stack else stack[ 0 ][ 1 ]

    if __name__ == '__main__':
        solution = Solution()
        ans = solution.match( input() )
        print( "Success" ) if ans == 0 else print( ans )