大家好，又見面了，我是你們的朋友全棧君。
實作括号比對算法（順序表）
括号比對問題
假設一個算術表達式中包含圓括号、方括号和花括号三種類型的括号，編寫一個函數，用來判别表達式中的括号是否正确配對，并設計一個測試主函數。
【算法思想】
在算術表達式中，右括号和左括号比對的次序正好符合後到的括号要最先被比對的“後進先出”堆棧操作特點，是以可以借助一個堆棧來進行判斷。
括号比對共有以下4種情況：
- 左、右括号配對次序不正确；
- 右括号多于左括号；
- 左括号多于右括号：
- 左、右括号比對正确。
具體方法如下：順序掃描算術表達式（表現為一個字元串），當遇到3種類型括号的左括号時，讓該括号進棧。當掃描到某一種類型的右括号時，比較目前棧頂括号是否與之比對，若比對，則退棧繼續進行判斷：若目前棧頂括号與目前掃描的括号不相同，則左、右括号配對次序不正确；若字元串目前為某種類型右括号而堆棧已空，則右括号多于左括号：字元串循環掃描結束時，若堆枝非空（即堆枝中尚有某種類型左括号），則說明左括号多于右括号；如果未出現
上述3種情況，則說明左、右括号比對正确。
我定義了新的頭檔案SeqList.h,再建立C源檔案檔案。
實際操作如下：
①建立SeqList.h頭檔案
②建立結構體
#ifndef _SeqStack_H_
#define _SeqStack_H_
#include<stdio.h>
#define MaxStackSize 100
typedef struct
{
DataType stack[MaxStackSize];
int top;
}SeqStack; 複制
③建立順序表
//初始化
void StackInitiate(SeqStack* S)//初始化順序堆棧S
{
S->top = 0;//初始化棧頂下标值
}
int StackNotEmpty(SeqStack S)
//判斷順序堆棧 S 非空否，非空則傳回 1，否則傳回 0
{
if (S.top <= 0)return 0;
else return 1;
}
//入棧
int StackPush(SeqStack* S, DataType x)
//把資料元素值 x 存入順序堆棧 S 中，入棧成功則傳回 1，否則傳回 0
{
if (S->top >= MaxStackSize)
{
printf("堆棧已滿無法插入！\n");
return 0;
}
else
{
S->stack[S->top] = x;
S->top++;
return 1;
}
}
//出棧
int StackPop(SeqStack* S, DataType* d)
//取出順序堆棧S的棧頂資料元素值由參數d帶回，出棧成功則傳回1，否則傳回0
{
if (S->top <= 0)
{
printf("堆棧已空無資料元素出棧！\n");
return 0;
}
else
{
S->top--;
*d = S->stack[S->top];
return 1;
}
}
//取棧頂資料元素
int StackTop(SeqStack S, DataType* d)
{
if (S.top <= 0)
{
printf("堆棧已空！\n");
return 0;
}
else
{
*d = S.stack[S.top - 1];
return 1;
}
}
#endif // ! _SeqStack_H_ 複制
主函數，如下：
#include<string.h>
#include<stdio.h>
#define MaxStackSize 100
typedef char DataType;
#include"SeqStack.h"
void ExpIsCorrect(char exp[], int n)
{
SeqStack myStack;
int i;
char c;
StackInitiate(&myStack);
for (i = 0; i < n; i++)
{
if ((exp[i] == '(') || (exp[i] == '[') || (exp[i] == '{'))
StackPush(&myStack, exp[i]);
else if (exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '(')
StackPop(&myStack, &c);
else if (exp[i] == ')' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '(')
{
printf("左右括号配對次序不正确！\n");
return;
}
else if (StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '[')
StackPop(&myStack, &c);
else if (exp[i] == ']' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '[')
{
printf("左右括号次序不正确！\n");
return;
}
else if (StackNotEmpty(myStack) && StackTop(myStack, &c) && c == '{')
StackPop(&myStack, &c);
else if (exp[i] == '}' && StackNotEmpty(myStack) && StackTop(myStack, &c) && c != '{')
{
printf("左右括号配對次序不正确！\n");
return;
}
else if (((exp[i] == ')') || (exp[i] == ']') || (exp[i] == '}')) && !StackNotEmpty(myStack))
{
printf("右括号多于左括号！\n");
return;
}
}
if (StackNotEmpty(myStack))
printf("左括号多于右括号！\n");
else
printf("左右括号比對正确！\n");
}
void main(void)
{
int i,n;
char x[MaxStackSize];
SeqStack myStack;
StackInitiate(&myStack);
printf("括号比對器\n");
printf("輸入字元串長度：\n");
scanf_s("%d", &n);
printf("輸入字元串：\n");
for (i = 0; i < n; i++)
{
scanf_s("%c", &x[i]);
}
n = strlen(x);
ExpIsCorrect(myStack.stack, n);
return;
} 複制
此方法為我的學習記錄，僅供參考。
釋出者：全棧程式員棧長，轉載請注明出處：https://javaforall.cn/129137.html原文連結：https://javaforall.cn