中英 网站模板 带手机版,定制一个企业网站多少钱,花店网站建设环境分析,网站开发待遇怎么样目录
一、栈的括号匹配
二、代码实现
1.方法创建
2.数据测试
3.完整的程序代码
总结 一、栈的括号匹配
要完成今天的任务#xff0c;需要先来了解一下什么是栈的括号匹配。首先#xff0c;顾名思义#xff0c;括号匹配就是指将一对括号匹配起来#xff0c;我们给定一…目录
一、栈的括号匹配
二、代码实现
1.方法创建
2.数据测试
3.完整的程序代码
总结 一、栈的括号匹配
要完成今天的任务需要先来了解一下什么是栈的括号匹配。首先顾名思义括号匹配就是指将一对括号匹配起来我们给定一个字符串字符串中除了各类括号也可以有别的字符将字符串中的所有括号都根据规则对应的一对左括号与右括号按“先左后右”的顺序匹配起来这个过程即为括号匹配。
在判断括号匹配时需要注意一些细节
必须是对应的一对左括号与右括号即“ ”与“ ”对应“ [ ”与“ ] ”对应“ { ”与“ } ”对应。必须是“一左一右”不能两个均为左括号或者两个均为右括号即“ ”与“ ”可以匹配但是“ ”与“ ”不匹配“ ”与“ ”也不匹配。必须按“先左后右”的顺序即“ ”匹配但是“ ”就不匹配。括号匹配遵循就近原则以当前括号的左边第一个括号为准。比如在下面的字符串中设第6个括号为当前括号那么就以该括号左边第一个括号为准即以第5个括号为准所以5、6成功匹配。可以看到在下图中第6个括号与第3个括号也满足了以上三个基本条件但是因为就近原则的存在所以3、6不匹配。同理如果第5个括号改为了“ [ ”或者“ { ”那么5、6也不会匹配。 括号匹配遵循匹配消除原则一旦某一对括号匹配成功那么该对括号就“消除”继续匹配后面的括号。比如在上图中5、6成功匹配后“消除”然后4、7继续匹配再比如“ { [ ( ) ] } ”也是匹配的。所给字符串中的全部括号都匹配成功才算完成了括号匹配比如“ [ { ( [ ( ) ] ) } ] ”是匹配的但是“ ( [ { ( [ ] ) ] ] ) ”就不匹配。在所给的字符串中除了各类括号也可以有别的字符比如“ 10 / { [ 4 - ( 5 - 2 ) ] * 2 } ”也是匹配的。
二、代码实现
弄清楚基本概念后就可以进行代码实现了。根据“先左后右”的顺序要求以及匹配消除原则我们可以按如下步骤进行括号匹配因为别的非括号字符对于括号匹配不起任何作用所以直接视为透明就行
遇到左括号“ ”、“ [ ”、“ { ”就直接入栈在栈中存放遇到右括号“ ”、“ ] ”、“ } ”就从栈中弹出栈顶元素与该右括号进行匹配如果二者匹配成功就“消除”继续匹配后面的括号如果二者匹配不成功直接输出不匹配即可
不过需要注意一点由于要求的是字符串中的全部括号均匹配才算成功所以如果匹配完毕后发现栈中仍然还存在左括号或者栈不空那么也算作匹配失败。
对于这个问题我们当然可以选择在匹配完毕后直接判断栈是否为空但是我们也可以采取另一种方式即在进行括号匹配之前入栈一个非括号字符作为栈底元素再在匹配完毕后进行出栈操作判断此时出栈的元素是否为该非括号字符如果是则说明字符串中的全部括号均已匹配如果不是则直接返回不匹配。
1.方法创建
进行代码模拟时我们只需要在昨天的代码基础上增加一个括号匹配的方法即可如下 /************************ Is the bracket matching?* * param paraString The given expression.* return Match or not.**********************/public static boolean bracketMatching(String paraString) {// Step 1. Initialize the stack through pushing a # at the bottom.CharStack tempStack new CharStack();tempStack.push(#);char tempChar, tempPoppedChar;// Step 2. Process the string. For a string, length() is a method// instead of a member variable.for(int i 0; i paraString.length(); i) {tempChar paraString.charAt(i);switch(tempChar) {case (:case [:case {:tempStack.push(tempChar);break;case ):tempPoppedChar tempStack.pop();if(tempPoppedChar ! () {return false;} // of ifbreak;case ]:tempPoppedChar tempStack.pop();if(tempPoppedChar ! [) {return false;} // of ifbreak;case }:tempPoppedChar tempStack.pop();if(tempPoppedChar ! {) {return false;} // of ifbreak;default:// Do nothing} // of switch} // of for itempPoppedChar tempStack.pop();if(tempPoppedChar ! #) {return false;} // of ifreturn true;} // of bracketMatching
首先定义括号匹配的方法bracketMatching其中String类型的参数paraString即为要输入的字符串再创建一个栈并入栈一个#将# 作为栈底的非括号字符。
然后利用charAt()方法for循环将字符串中的字符一个一个读取出来。 补充 length()方法作用是返回字符串的长度调用格式为字符串名.length() charAt()方法作用是获取字符串中指定索引值的字符调用格式为字符串名.charAt(指定索引值) 根据之前的分析这里需要进行读取字符的判断且判断分支较多符合switch语句适用的情况单一变量的多个不同取值问题所以我们采用了switch语句。
匹配完毕后进行出栈操作并判断此时出栈的元素是否为#如果不是则直接返回false如果是则返回true。
2.数据测试
下面我们进行数据测试这里用到了以下五个数据
[ 2 (1 - 3) ] * 4( ) )( ) ( ) ( ( ) )( { } [ ] )) (
显然通过直接思考可以预测第1、3、4个字符串是匹配的剩下的是不匹配的。 /************************The entrance of the program.** param args Not used now.**********************/public static void main(String[] args) {CharStack tempStack new CharStack();for(char ch a; ch m; ch) {tempStack.push(ch);System.out.println(The current stack is: tempStack);} // of for chchar tempChar;for(int i 0; i 12; i) {tempChar tempStack.pop();System.out.println(Popped: tempChar);System.out.println(The current stack is: tempStack);} // of for iboolean tempMatch;String tempExpression [2 (1 - 3)] * 4;tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression ( ) );tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression ()()(());tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression ({}[]);tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression )(;tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);} // of main
3.完整的程序代码
package datastructure;/***Char stack. I do not use Stack because it is already defined in Java.**auther Xin Lin 3101540094qq.com.*/public class CharStack {/*** The depth.*/public static final int MAX_DEPTH 10;/*** The actual depth.*/int depth;/*** The data.*/char[] data;/************************ Construct an empty char stack.**********************/public CharStack() {depth 0;data new char[MAX_DEPTH];} // of the first constructor/************************ Overrides the method claimed in Object, the superclass of any class.**********************/public String toString() {String resultString ;for (int i 0; i depth; i) {resultString data[i];} // of for ireturn resultString;} // of toString/************************ Push an element.* * param paraChar The given char.* return Success or not.**********************/public boolean push(char paraChar) {if (depth MAX_DEPTH) {System.out.println(Stack full.);return false;} // of ifdata[depth] paraChar;depth;return true;} // of push/************************ Pop an element.* * return The popped char.**********************/public char pop() {if(depth 0) {System.out.println(Nothing to pop.);return \0;} // of ifchar resultChar data[depth - 1];depth--;return resultChar;} // of pop/************************ Is the bracket matching?* * param paraString The given expression.* return Match or not.**********************/public static boolean bracketMatching(String paraString) {// Step 1. Initialize the stack through pushing a # at the bottom.CharStack tempStack new CharStack();tempStack.push(#);char tempChar, tempPoppedChar;// Step 2. Process the string. For a string, length() is a method// instead of a member variable.for(int i 0; i paraString.length(); i) {tempChar paraString.charAt(i);switch(tempChar) {case (:case [:case {:tempStack.push(tempChar);break;case ):tempPoppedChar tempStack.pop();if(tempPoppedChar ! () {return false;} // of ifbreak;case ]:tempPoppedChar tempStack.pop();if(tempPoppedChar ! [) {return false;} // of ifbreak;case }:tempPoppedChar tempStack.pop();if(tempPoppedChar ! {) {return false;} // of ifbreak;default:// Do nothing} // of switch} // of for itempPoppedChar tempStack.pop();if(tempPoppedChar ! #) {return false;} // of ifreturn true;} // of bracketMatching/************************The entrance of the program.** param args Not used now.**********************/public static void main(String[] args) {CharStack tempStack new CharStack();for(char ch a; ch m; ch) {tempStack.push(ch);System.out.println(The current stack is: tempStack);} // of for chchar tempChar;for(int i 0; i 12; i) {tempChar tempStack.pop();System.out.println(Popped: tempChar);System.out.println(The current stack is: tempStack);} // of for iboolean tempMatch;String tempExpression [2 (1 - 3)] * 4;tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression ( ) );tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression ()()(());tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression ({}[]);tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);tempExpression )(;tempMatch bracketMatching(tempExpression);System.out.println(Is the expression tempExpression bracket matching? tempMatch);} // of main
} // of class CharStack
运行结果 可以发现运行结果与我们之前的预测是完全相同的。
总结
总体来说今天学习的内容不是很复杂简单来说就是对昨天栈的入栈出栈等操作进行一个应用而且根据今天代码的难度其实可以知道括号匹配算是栈的一个基本应用不过它也是一个非常重要的应用在今后很多算法和问题中都会涉及到。
