title: Leetcode 20.有效的括号
hidden: true
date: 2019-04-26 13:01:55
tags:

- C++
- Leetcode
- 栈

categories: Leetcode

mathjax: false

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。
    3. 注意空字符串可被认为是有效字符串。

示例 1:

    输入: "()"
    输出: true

示例 2:

    输入: "()[]{}"
    输出: true

示例 3:

    输入: "(]"
    输出: false

示例 4:

    输入: "([)]"
    输出: false

示例 5:

    输入: "{[]}"
    输出: true

题目分析

使用栈来读取每个括号, 如果栈顶的括号与将压入的括号相对, 则弹出栈顶元素, 否则入栈.

最后检查是否栈为空, 如非空则为非法字符串.

源码

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 != 0) return false;
        // 如果字符串字符数目为奇数则一定有单个的括号
        stack<char>* st = new stack<char>(); // 新建指针以便结束时删除
        st->push('1');
        for(int i=0; i<s.size(); ++i) {
            if(st->top() == s[i]-1 || st->top() == s[i]-2) {
                st->pop();
            }else {
                st->push(s[i]);
            }
        }
        bool a = st->top() == '1';
        delete st;
        return a;
    }
};