[データ構造]括弧マッチング問題解決報告
2317 ワード
Problem Description
演算式には、丸括弧、大かっこの2種類が含まれていると仮定して、かっこが合っているかどうかを判定するプログラムを作成してみます.マッチングは
丸かっこ、大かっこの2種類のかっこを含む演算式出力
マッチング出力
演算式には、丸括弧、大かっこの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;
}