题目表述

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

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

示例1

输入: "()"
输出: true

示例2

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

示例3

输入: "(]"
输出: false

示例4

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

分析

这是一道典型的栈结构的题,因为它体现了LIFO特性

思路一

  1. 首先要先往栈里放一个元素
  2. 紧着利用for循环,比较接下来的字符是否可以栈顶元素匹配成一对括号,如果不可以,则将其也压如栈中;如果可以,就将栈顶元素出栈
  3. 当for循环结束时,如果栈不为空,则输出false,否则输出true

思路二

  1. 构造两个栈,左括号放入栈一,右括号放入栈二
  2. 当放入结束后,开始同时从两个栈取出元素,如果有一对不匹配,则返回false
  3. 当两个栈全为空时,依旧没有return,则返回true

参考代码(这里只提供思路一)


class Solution {
public:
bool isValid(string s) {
stack<char> result;
int n=s.size();
if(n==0) return true;
for(int i=0;i<n;i++)
{
if(result.empty())
result.push(s[i]);
else if(result.top()=='('&&s[i]==')'||
result.top()=='['&&s[i]==']'||
result.top()=='{'&&s[i]=='}')
result.pop();
else
result.push(s[i]);

}
return result.empty();
}
};

谢谢访问