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;
}