A : DS堆栈--括号匹配

Description

处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：

(   )   [   (   )   (   [   ]   )   ]   {   }
1   2   3   4   5   6   7   8   9   10  11  12

从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：

1. 当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。
2. 当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除
3. 若到最后，括号不能完全匹配，则说明输入的表达式有错

建议使用C++自带的stack对象来实现

Input

第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入

Output

对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error

Sample

Input

2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6

Output

ok
error

解题思路：

遇到左括号入栈，右括号出栈。匹配的情况下遍历完成后栈是空的

如果栈空的时候遇到右括号，用flag记录， 判断输出error

如果遍历完表达式，栈不空，则说明不匹配，输出error

代码：

#include 
#include 
#include 
using namespace std;
int main() {
	int t;
	cin >> t;
	string str;
	int len;
	while (t--) {
		stack<char> s;
		cin >> str;
		len = str.length();
		bool flag = true;
		for (int i = 0; i < len; i++) {
			if (str[i] == '('  ||
				str[i] == '['  ||
				str[i] == '{' ) {
				s.push(str[i]);
			}
			else if (!s.empty() && (str[i] == ')' && s.top() == '('
					|| str[i] == '}' && s.top() == '{'
					|| str[i] == ']' && s.top() == '[')) {
				s.pop();
			}
			else if(str[i] == ')'|| str[i] == '}'|| str[i] == ']' ) {
				flag = false;
				break;
			}
		}
		if (!s.empty() || flag==false) {
			cout << "error" << endl;	
		}
		else {
			cout << "ok" << endl;
		}
	}
}