当前位置:码农谷 > 算法与程序 > 括号匹配的程序源码(完整源码)

括号匹配的程序源码(完整源码)

所属学科:Java语言 难度: 关注度:673

一、括号匹配

括号匹配是程序设计中一个最基本的问题。例如,在Java语言中,for循环语言中的循环体需要用一对花括号“{}”括起来,示例如下:

类似的还有if语句,switch语句等复合语句及自定义函数。

在C语言的编译环境中^入代码时,要求括号成对出现;否则,编译时将提示出错信息。例如:

在上述代码中,if语句的第一个花括号缺少匹配,因此将无法通过编译。 

编译系统具有括号匹配的一个检测功能。那么括号匹配的功能是如何实现的呢?

1.1  括号匹配算法

先来分析一下括号匹配问题。括号匹配的一个基本规则是括号应该成对出现,并且可以进行嵌套。可以使用的括号包括如下几种:

•花括号“{}”;

•方括号“[]”;

•圆括号“()”;

•尖括号“<>”。

这些括号往往成对出现,因此可以具体分为左括号和右括号。

•左括号:和“{”、“[”、“(”和“<”。< p="">

•右括号:和“}”、“]”、“)”和“>”。

根据前述的括号匹配原则,可知如下几种形式都是匹配的:

[]、{[]}、{[[()]<>]}等。

而以下几种则是不匹配的情况:

[]{>{}、(){}><>}、}[><()等。< p="">

判断括号匹配用到了栈结构,其操作步骤如下:

(1)输入1个字符,当该字符是括号字符时,程序进入循环处理。

(2)如果是左括号,则将其入桟,继续执行步骤(1)。

(3)如果是右括号,则取出栈顶数据进行对比,如果匹配则不进行操作;否则必须先将刚才取出的栈顶数据重新入栈,再将刚才输入的括号字符也入栈。

(4)然后再输入下一个字符,重复执行,直到所有的字符都得到操作。按照此思路便可以编写相应的算法来判断括号是否匹配。代码示例如下:

由于这里需要用到栈结构,因此首先定义了栈结构类型Stack。数据项data为栈内数据,数据项top为栈顶引用,maxSize为栈大小。

方法pipei()便是判断括号是否匹配的算法。在程序中,循环对比每个输入的字符来判断是否匹配,然后进行相应的处理。该程序严格遵循了前述的算法,读者可以对照着加深理解。最后,如果栈为空,表示所有的括号都匹配;否则表示有不匹配的括号,输出显示结果。

1.2  括号匹配求解

学习了前面括号匹配算法之后,便可以完成括号匹配的判断问题^由于需要使用栈结构,读者可以参阅前面章节中的介绍。下面给出一个完整的例子来演示括号匹配判断的过程。完整的程序代码示例如下:

在上述代码中,用到了栈结构,包括初始化栈、入栈和出栈等操作。读者可以参阅前面章节的介绍来理解。在主方法中,首先调用pipei()方法,输入一组括号组合,以0表示结束,支持的括号包括“{}”、“[]”“()”和“<>”。方法pipei()进行判断并输出结果。

该程序可以执行多次。执行该程序,输入相应的括号组合,得到结果。

程序源码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
 
/**
 * 使用数组实现堆栈,包括入栈、出栈、获取堆栈长度、 
 *
 */ 
class Stack {       
    char[] data; 
    int maxSize;   
    int top;      
 
    Scanner input=new Scanner(System.in);
    public Stack(int maxSize)
    {       
        this.maxSize = maxSize;       
        data = new char[maxSize];       
        top = -1;       

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1