[データ構造]括弧マッチング問題解決報告

2317 ワード

Problem Description
演算式には、丸括弧、大かっこの2種類が含まれていると仮定して、かっこが合っているかどうかを判定するプログラムを作成してみます.マッチングはMatch succeed!に戻ります.そうでないとMatch false!に戻ります.例[1+2*(3+4*(5+6))]カッコマッチング(1+2)*(1+2*[(1+2)+3)カッコ不一致入力
丸かっこ、大かっこの2種類のかっこを含む演算式出力
マッチング出力Match succeed!不一致出力Match false!例入力[1+2* (3+4*(5+6))]出力Match succeed!テスト入力
[1+2*(3+4*(5+6))]
テスト出力
Match succeed!
AcCode
//
//  main.cpp
//      
//
//  Created by jetviper on 2017/3/26.
//  Copyright © 2017  jetviper. All rights reserved.
//


#include 
#include 
#include 
#include
#define true 1
#define false 0

typedef struct Node
{
    char data;
    struct Node *pNext;
}NODE, *PNODE;

typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK, *PSTACK;
//     
void init(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    pS->pBottom = pS->pTop;
    pS->pTop->pNext = NULL;
    return;
}
//       
void push(PSTACK pS, char val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = pS->pTop;
    pS->pTop = pNew;
    return;
}
//       
int empty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom)
    {
        return true;
    }
    else
        return false;
}

void deltop(PSTACK pS) {
    pS->pTop = pS->pTop->pNext;
    return;
}

int main(void)
{
    STACK S;
    PSTACK ps=&S;
    init(&S);
    char val;
    char str[100];
    scanf("%s", &str);
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == '(' || str[i] == ')' || str[i] == '[' || str[i] == ']') {
            val = ps->pTop->data;
            
            if (str[i] == '(' || str[i] == '[')push(&S, str[i]);
            else if (val=='(' && str[i]==')'||val=='['&&str[i]==']')deltop(&S);
            else push(&S, str[i]);
        }
    }
    
    if (empty(&S))
    {
        printf("Match succeed!
"); } else { printf("Match false!
"); } return 0; }