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.

二. 题目分析

输入一串括号字符串，仅仅包含 (]} 这三种括号。判断输入的括号字符串是不是合法的，合法的输出true，不合法输出false。要求”()”、”[]”、”{}”必须成对使用，或者是像”({[]})”这种层层嵌套但保持对称的，也属于合法。

这一题是典型的使用压栈的方式解决的问题，解题思路如下：

1. 计数 i = 0
2. 根据字符指针取出括号字符串的当前字符，如果当前字符为空，跳到5
3. 如果当前字符是左括号( (]}这三种 )，直接压入栈
4. 如果当前字符是右括号( )]}这三种 )，从栈中弹出一个元素，弹出的元素如果和当前字符匹配，i++，回到2；否则，返回false
5. 如果栈为空，返回true；否则返回false。

三. 示例代码

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class Solution
{
public:
    bool isValid(string const& s)
    {
        if (s.size() == 0)
            return false;
        stack<char> temp;
        for (size_t i = 0; i < s.size(); ++i)
        {
            if (s[i] == ")" || s[i] == "]" || s[i] == "}")
            {
                if (temp.empty())
                    return false;
                else
                {
                    char k = temp.top();
                    temp.pop();
                    if ((k == "(" && s[i] != ")") || (k == "[" && s[i] != "]") || (k == "{" && s[i] != "}"))
                        return false;
                }
            }
            else if (s[i] == "(" || s[i] == "[" || s[i] == "{")
                temp.push(s[i]);
            else return false;
        }
        return temp.empty(); // 只有当最后栈为空时才说明输入字符串是有效的
    }
};

简单的测试代码：

#include "ValidParentheses.h"

int main()
{
    cout << "Please input a string (only the characters "(’, ’)’, ’{’, ’}’, ’[’ and ’]’): " << endl;
    string input;
    cin >> input;
    Solution s;
    bool result = s.isValid(input);
    cout.setf(ios::boolalpha);
    cout << "The result is: " << result << endl;
    system("pause");
    return 0;
}

四. 小结

这道题需要对括号字符串的每个字符都遍历一遍，因此时间复杂度是O(n)。