1/12 每日C 使用Stack處理左右括弧

20. Valid Parentheses

Solved

Easy

Topics

Companies

Hint

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 10000

//stack結構

struct stack{

    char data[MAX_SIZE];

    int top;

};

typedef struct stack Stack;

//改名叫Stack

//初始化堆疊

void init_Stack(Stack *stack){

    stack->top = -1;

}

//定義空堆疊

bool isEmpty(Stack *stack){

    return stack->top == -1;

}

//定義堆疊滿了

bool isFull(Stack *stack){

    return stack->top == MAX_SIZE-1;

}

//推入

void push(Stack *stack,char str){

    if (isFull(stack)){

        printf("這個堆疊滿了\n");

        return ;

    }

    stack->data[++stack->top]=str;

}

//彈出

char pop(Stack *stack){

    if(isEmpty(stack)){

        printf("是空集合\n");

        exit(EXIT_FAILURE);

    }

    return stack->data[stack->top--];

}

char peek(Stack *stack){

    if(isEmpty(stack)){

        printf("是空集合\n");

        exit(EXIT_FAILURE);

    }

    return stack->data[stack->top];

}

bool isValid(char* s) {

    int i=0;

    char tmp;

    Stack stack;

   

    //初始化

    init_Stack(&stack);

    while (*s!='\0'){

        if (*s=='(' || *s=='[' || *s=='{'){

            push(&stack,*s);

        }

        else

            {

                if (isEmpty(&stack)){

                    return false;

                }

                tmp=pop(&stack);

                if (tmp=='(' && *s!=')'){

                    return false;

                }

                else if (tmp=='[' && *s!=']'){

                    return false;

                }

                else if (tmp=='{' && *s !='}')

                    return false;

            }

        s++;

    }

    if (isEmpty(&stack))

        return true;

    else

        return false;

   

}