LeetCode Valid Parentheses判断括号是否配对

Valid Parentheses

Given a string containing just the characters'(',')','{','}','['and']', determine if the input string is valid.

The brackets must close in the correct order,"()"and"()[]{}"are all valid but"(]"and"([)]"are not.

对栈熟悉的，一开始就会想到栈的应用了。

严慧敏那本书也介绍了差不多的栈应用。

思路应该很好想：

1 利用一个栈保存string s里面的字符

2 判断如果左括号(,{,[入栈，如果右括号]})，与栈顶成对就进栈，不成对就入栈，如果此时栈为空，可以提前判断返回false

3 最后判断栈是否为空，空返回真，非空返回假。

我这里增加一个额外函数把这些括号转换为整数，以方便判断第二种情况，使得程序更加简洁。

class Solution {
public:
	bool isValid(string s) 
	{
		stack<char> stk;

		for (int i = 0; i < s.length(); i++)
		{
			switch (s[i])
			{
			case '(': case '{': case '[':
				stk.push(s[i]);
				break;
			case ')': case '}': case ']':
				if (!stk.empty())
				{
					if (cToInt(stk.top()) + cToInt(s[i]) == 0) stk.pop();
					else stk.push(s[i]);
				}
				else if (stk.empty())
				{
					return false;
				}
				break;
			default:
				break;
			}
		}
		return stk.empty();
	}

	int cToInt(char c)
	{
		switch (c)
		{
		case '(':
			return -3;
		case '{':
			return -2;
		case '[':
			return -1;
		case ']':
			return 1;
		case '}':
			return 2;
		case ')':
			return 3;
		default:
			break;
		}
	}
};