UVa 673

Parentheses Balance

from Volume 2. Data Structures :: Lists

Description

输入一个只含有 ‘(’ 、‘)’ 、‘[’ 、‘]’ 的序列，判断并输出括号是否匹配。

Solution

经典的括号匹配问题，用一个栈来存放括号。左括号则入栈，右括号则出栈。匹配会有几种情况：

• 缺少括号。
• 多余括号。
• 括号匹配错误。

分别对应括号出入栈时的几种情况：

• 括号要出栈时，栈已经为空。
• 序列读完后，栈不为空。
• 括号要出栈时，栈顶元素不是要出栈的括号。