括号比對---棧的應用

輸入一個表達式，表達式中包括三種括号“（）”、“[]”和“{}”，判斷該表達式的括号是否比對。

//括号比對 
#include <stdio.h>
#include <string.h>
typedef struct Stack{
	char base[200];
	int top;
	int Stacksize;
}Stack;

void InitStack(Stack &S)
{//建立一個空棧
	S.Stacksize=200;
	S.top=0;
}

void Push(Stack &S,char ch)
{//入棧操作
	if(S.top+1>S.Stacksize)
	{
		printf("棧滿，操作失敗.");
		return ;
	}
	S.base[S.top++]=ch;
}

void top(Stack &S,char &ch)
{//出棧操作
	ch=S.base[--S.top];
}

int StackEmpty(Stack S)
{//判斷棧是否為空
	if(S.top==0)
		return 1;
	return 0;
}

int Judge(char *str,Stack &S)
{//判斷括号是否比對
	int len,i,j;
	char ch;
	len=strlen(str);
	for(i=0;i<len;i++)
	{
		if(str[i]=='[' || str[i]=='(' || str[i]=='{')
			Push(S,str[i]);
		
		else if(str[i]== ']' || str[i]== ')' ||str[i]== '}')
		{
			if(StackEmpty(S))
				return 0;
			top(S,ch);
			if(str[i]==')' && ch=='(' || str[i]=='}' && ch=='{' || str[i]==']' && ch=='[')
				continue;
		    else
		    	return 0;	
		}
	}
        if(StackEmpty(S))
            return 1;
        else
            return 0;
}

int main()
{
	Stack S;
	char str[100];
	int judge;
	InitStack(S);
	printf("請輸入算術表達式：");
	scanf("%s",str);
	judge=Judge(str,S);
	if(judge)
		printf("算數表達式括号正确\n");
	else
		printf("括号不比對。\n");
	
	return 0;
}