# 20. Valid Parentheses 筆記

這題是經典的推疊題目，以下先介紹簡單的堆疊。

## Stack(堆疊)

我們在資料結構中一定學過stack，其中可能有先進先出、後進先出等方法，透過下圖可以很簡單的了解到


上圖就是後進先出的例子，那以下透過程式來實現這方法

#include <stdio.h>
#include <stdlib.h>
#define MAXSTACK 100 /*定義最大堆疊容量*/
int stack[MAXSTACK];  //堆疊的陣列宣告 
int top=-1;		//堆疊的頂端
int isEmpty();
void push(int); 
int pop();
 
int main(int argc, char *argv[]) {
	int value;
	int i;
	printf("請依序輸入10筆資料:\n");
	for(i=0;i<10;i++){
		scanf("%d",&value);
		push(value);
	}
	printf("====================\n");
	while(!isEmpty()){
		printf("堆疊彈出的順序為:%d\n",pop()); 
	}
	pop();
	return 0;
}
/*判斷是否為空堆疊*/
int isEmpty(){
	if(top==-1){
		return 1; 
	}else{
		return 0;
	}
} 
/*將指定的資料存入堆疊*/
void push(int data){
	if(top>=MAXSTACK){
		printf("堆疊已滿,無法再加入\n");	
	}else{
		top++;
		stack[top]=data;
	}
 
} 
/*從堆疊取出資料*/
int pop(){
	int data;
	if(isEmpty()){
		printf("堆疊已空\n");
	}else{
		data=stack[top];
		top--;
		return data; 
	}
}

## 題目

在C語言中沒有堆疊相關程式，在Cpp中有支援，那在這邊就直接用模擬的方式利用top計數器來表示目前堆疊的位置，來比對是否()[]{}有對應到，第一個(進去之後top就+1，後面的比對就看看右括號是否剛好有對應，有對應到就把計數器降回去，這樣就可以一直對應順序了，這邊非常漂亮的實作了Stack。

寫了這題才發現自己有多麼不熟悉實作。

bool isValid(char * s){
    char *stack = (char *)malloc((int)s*sizeof(char));
    if(strlen(s)==0)return true;
    if(strlen(s)%2==1)return false;
    int top = 0;
    for(int i = 0; i < strlen(s); i++){
        if(s[i]=='[' || s[i]=='{' || s[i]=='('){
            stack[top] = s[i];
            top++;
        }
        else if(s[i] == ')'){
            if(top==0)
                return false;
            else if(stack[top-1] == '('){
                top--;
            }
            else{
                return false;
            }
        }
        else if(s[i] == ']'){
            if(top==0)
                return false;
            else if(stack[top-1] == '['){
                top--;
            }
            else{
                return false;
            }
        }
        else if(s[i] == '}'){
            if(top == 0)
                return false;
            else if(stack[top-1] == '{'){
                top--;
            }
            else{
                return false;
            }
        }
        else{
            return false;
        }
        }
        return top==0 ? true : false;
}

###### tags: `LeetCode`