[LeetCode]Valid Parentheses

Q：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），則彈出棧頂字符；若當前字符優先級小於棧頂字符（0），則當前字符入棧。最後觀察棧是否為空，若為空，則括弧配對，否則不配對。優先級表如下圖：

下面貼上代碼：

#include 
#include
using namespace std;

class Solution {
public:
	int replace(char c){
		if (c == '(')
			return 0;
		if (c == ')')
			return 1;
		if (c == '[')
			return 2;
		if (c == ']')
			return 3;
		if (c == '{')
			return 4;
		if (c == '}')
			return 5;
	}
	bool isValid(string s) {
		if (s.length() == 0 || s.length() == 1)
			return false;
		int ch[6][6] = { { 0, 1, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 1, 0, 0 },
		{ 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 1 },
		{ 0, 0, 0, 0, 0, 0 }
		};
		stack ss;
		for (int i = 0; i < s.length(); i++){
			if (ss.empty()){
				ss.push(s[i]);
				continue;
			}
			char c = ss.top();
			if (ch[replace(c)][replace(s[i])])
				ss.pop();
			else
				ss.push(s[i]);
		}
		if (ss.empty())
			return true;
		else
			return false;
	}
};

int main() {
	Solution s;
	cout << s.isValid("()[]{}()") << endl;
	cout << s.isValid("(([]{}))") << endl;
	cout << s.isValid("([]}") << endl;
	return 0;
}