数据结构与算法判断括号是否匹配

心已赠人 2022-05-26 03:38 158阅读 0赞

数据结构与算法 判断括号是否匹配

一、简单说明

判断表达式中的半弧括号是否匹配，例如:"(56-20)/(4+2)"、"(1+(56-20)/(4+2))-(2\*3)"中的括号是否匹配。

二、效果

![20180424164951712][]

三、主要思路

1、定义一个栈用来存储左括号'('。

2、扫描表达式，当字符为'('时,进栈。(只有'('进栈)

3、当字符为')'时，先判断栈是否为空，为空则不匹配，结束判断；若不为空，则出栈一个'(';

4、扫描结束、若栈为空则匹配，不为空则比匹配。

四、举例(56-20)/(4+2)

![2018042416364453][]

五、源文件

match.c文件

#include <stdio.h>
    #include <string.h>//strlen函数所在库
    #include <stdlib.h> //memset函数所在库 
    #define SIZE 100   //定义栈空间大小 
    
    struct    //匿名结构体、用来存储左括号 
    {
    	int data[SIZE];
    	int top;
    }stack;
    
    int main()
    {
    	char exp[] = "(56-20)/(4+2)";//运算表达式 
    	int length = strlen(exp);//计算表达式的长度 
    	int flag = 1;//标志是否匹配，1为匹配 
    	
    	//栈初始化
    	memset(&stack,0,SIZE) ;//清零
    	stack.top = -1;
    	 
    	int i = 0;
    	for(i = 0;i<length;i++)
    	{
    		if(exp[i]=='(')//如果是'('进栈 (只有'('才能进栈)
    		{
    			stack.data[++stack.top] = exp[i];
    		}
    		else if(exp[i]==')')//如果是')'出栈
    		{
    			if(stack.top == -1)//如果栈空、没有与该右括号匹配，跳出循环 
    			{
    				flag = 0;
    				break; 
    			} 
    			else       //如果栈不为空、与该右括号匹配、出栈(栈中只有'(') 
    			{
    				--stack.top; 
    			}
    			
    		}
    		
    	} 
    	
    	if(flag && stack.top== -1)
    	{
    		printf("匹配\n");
    	}
    	else
    	{
    		printf("不匹配\n");
    	}
    	 
    	getchar(); 
    	return 0;
    }

[20180424164951712]: /images/20220526/27d07ef28fc04b438408d67354cfce3e.png
[2018042416364453]: /images/20220526/2a167ed8964c4ae68df5c30569bd9d34.png