Check Opening Brackets

用堆栈实现字符串中不匹配括号的检查,堆栈结构用 List 实现。
失配时输出 1 ,通过检查输出 Success。

Python 版本:

import sys

class Bracket:
    def __init__(self, bracket_type, position):
        self.bracket_type = bracket_type
        self.position = position

    def Match(self, c):
        if self.bracket_type == '[' and c == ']':
            return True
        if self.bracket_type == '{' and c == '}':
            return True
        if self.bracket_type == '(' and c == ')':
            return True
        return False

if __name__ == "__main__":
    text = sys.stdin.read()

    opening_brackets_stack = []                             #用List类型实现栈
    for i, next in enumerate(text):
        if next == '(' or next == '[' or next == '{':
            opening_brackets_stack.append((next, i))        #相当于push操作

        if next == ')' or next == ']' or next == '}':
            if not opening_brackets_stack:                  #第一个字符是三种右括号时
                opening_brackets_stack.append(False)        #随便放点东西到栈里面
                break                                       #方便输出时的判断
            else:
                (b, position) = opening_brackets_stack.pop()
                brckt = Bracket(b, position)
                if not brckt.Match(next):                   
                    opening_brackets_stack.append(False)
                    break

    if not opening_brackets_stack:                          #空栈意味着所有的左括号都已经出栈,
        print("Success\n")                                  #并且和右括号匹配了
    else:
        print("1\n")

C++ 版本:

注意 c++ 里面 std::stack::top() 方法要加上pop() 才等同于 Python 中的 pop(),比较恶心。

#include <iostream>
#include <stack>
#include <string>

struct Bracket {
    Bracket(char type, int position):       //初始化列表
        type(type),                 //the 1st "type" is private attr, the 2nd is passed-in variable.
        position(position)
    {}

    bool Matchc(char c) {
        if (type == '[' && c == ']')
            return true;
        if (type == '{' && c == '}')
            return true;
        if (type == '(' && c == ')')
            return true;
        return false;
    }

    char type;
    int position;
};

int main() {
    std::string text;
    getline(std::cin, text);

    std::stack <Bracket> opening_brackets_stack;
    for (int position = 0; position < text.length(); ++position) {
        char next = text[position]; 

        if (next == '(' || next == '[' || next == '{') {
            opening_brackets_stack.push(Bracket(next, position));
        }

        if (next == ')' || next == ']' || next == '}') {
            if (opening_brackets_stack.empty())
            {
                opening_brackets_stack.push(Bracket(next, position));
                break;
            }else
            {
                struct Bracket brckt = opening_brackets_stack.top();
                opening_brackets_stack.pop();
                if (!brckt.Matchc(next))
                {
                    //std::cout << brckt.type << std::endl;
                    opening_brackets_stack.push(Bracket(next, position));
                    break;
                }
            }
        }
    }

    if (opening_brackets_stack.empty())
    {
        std::cout << "Success" << std::endl;
    }else
    {
        std::cout << "1" << std::endl;
    }
    return 0;
}