今天終于開始看棧的部分咯！棧這個東西沒啥好介紹的，我想基本只要寫過一丟丟代碼的人已經(jīng)都非常清楚了。今天這個題目是一個非常簡單但是也很經(jīng)典地用到棧這個數(shù)據(jù)結構的題，廢話不多說，原題鏈接如下：

Loading...?leetcode.com

題目的要求是輸入一個只包含括號的字符串，涉及的括號包括小、中、大括號三種，返回字符串中的括號順序是否合法。實例如下：

棧先進后出的特征使得其非常適合這種涉及到對稱和合法性的場景，題目可以分解為以下幾種判斷：

• 如果先出現(xiàn)左括號，那么后面肯定還會有右括號，所以每當遇到左括號的時候就將其壓棧(PUSH)，接著往后找
• 每當遇到右括號時，先判斷此時棧是不是空的：
  • 如果棧是空的，那么肯定是還沒出現(xiàn)左括號就先出現(xiàn)右括號了，那么括號肯定就不對稱了；
  • 如果此時棧不為空，就彈出棧頂?shù)脑?POP)，看是不是對應的左括號，如果不是那么括號肯定也是不對稱的；否則接著往后判斷下一個括號
  • 所以括號遍歷完，最后判斷下棧是不是空的：棧為空說明字符串中所有括號都正確匹配了，返回True；否則返回False

根據(jù)上述思路，代碼如下：

class

注意：在Python里，List是可以直接當做stack使用，其提供的append和pop兩個方法就對應于棧的壓棧和出棧，而構建mapping表是為了查找對稱的括號更方便。整體的判斷思路大概就是這樣

總結

以上是生活随笔為你收集整理的栈判断字符串是否为中心对称_数据结构和算法入门之判断括号字符串的合法性(valid parentheses)...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。