括号匹配问题问题描述:分析创建一个栈用来存储左括号从左往右遍历字符串拿到每一个字符判断该字符是不是左括号如果是放入栈中存储判断该字符是不是右括号如果不是继续下一次循环如果该字符是右括号则从栈中弹出一个元素t判断元素t是否为null如果不是则证明有对应的左括号如果不是则证明没有对应的左括号循环结束后判断栈中还有没有剩余的左括号如果有则不匹配如果没有则匹配代码实现栈 Stack:importjava.util.Iterator;publicclassStackTimplementsIterableT{//记录首结点privateNodehead;//栈中元素的个数privateintN;privateclassNode{publicTitem;publicNodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}publicStack(){this.headnewNode(null,null);this.N0;}//判断当前栈中元素个数是否为0publicbooleanisEmpty(){returnN0;}//获取栈中元素的个数publicintsize(){returnN;}//把t元素压入栈publicvoidpush(Tt){//找到首结点指向的第一个结点NodeoldFirsthead.next;//创建新结点NodenewNodenewNode(t,null);//让首结点指向新结点head.nextnewNode;//让新结点指向原来的第一个结点newNode.nextoldFirst;//元素个数1N;}//弹出栈顶元素publicTpop(){//找到首结点指向的第一个结点NodeoldFirsthead.next;if(oldFirstnull){returnnull;}//让首结点指向原来第一个结点的下一个结点head.nextoldFirst.next;//元素个数-1N--;returnoldFirst.item;}OverridepublicIteratorTiterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateNoden;publicSIterator(){this.nhead;}OverridepublicbooleanhasNext(){returnn.next!null;}OverridepublicObjectnext(){nn.next;returnn.item;}}}匹配方法 isMatch():/** * 判断str中的括号是否匹配 * param str 括号组成的字符串 * return 如果匹配返回true如果不匹配返回false */publicstaticbooleanisMatch(Stringstr){//1.创建栈对象用来存储左括号StackStringcharsnewStack();//2.从左往右遍历字符串for(inti0;istr.length();i){StringcurrCharstr.charAt(i);//3.判断当前字符是否为左括号如果是则把字符放入到栈中if(currChar.equals(()){chars.push(currChar);}elseif(currChar.equals())){//4.继续判断当前字符是否是有括号如果是则从栈中弹出一个左括号并判断弹出的结果是否为null,如果为null证明没有匹配的左括号如果不为null则证明有匹配的左括号Stringpopchars.pop();if(popnull){returnfalse;}}}//5.判断栈中还有没有剩余的左括号如果有则证明括号不匹配if(chars.size()0){returntrue;}else{returnfalse;}}测试:publicstaticvoidmain(String[]args){Stringstr上海(长安)());booleanmatchisMatch(str);System.out.println(str中的括号是否匹配match);}逆波兰表达式求值问题逆波兰表达式求值问题是我们计算机中经常遇到的一类问题要研究明白这个问题首先我们得搞清楚什么是逆波兰表达式要搞清楚逆波兰表达式我们得从中缀表达式说起。中缀表达式中缀表达式就是我们平常生活中使用的表达式例如13*2,2-(13)等等中缀表达式的特点是二元运算符总是置于两个操作数中间。中缀表达式是人们最喜欢的表达式方式因为简单易懂。但是对于计算机来说就不是这样了因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级如果计算机执行中缀表达式需要解析表达式语义做大量的优先级相关操作。逆波兰表达式(后缀表达式)逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法后缀表达式的特点运算符总是放在跟它相关的操作数之后。需求给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式求出该逆波兰表达式的结果。分析代码实现栈 Stack:importjava.util.Iterator;publicclassStackTimplementsIterableT{//记录首结点privateNodehead;//栈中元素的个数privateintN;privateclassNode{publicTitem;publicNodenext;publicNode(Titem,Nodenext){this.itemitem;this.nextnext;}}publicStack(){this.headnewNode(null,null);this.N0;}//判断当前栈中元素个数是否为0publicbooleanisEmpty(){returnN0;}//获取栈中元素的个数publicintsize(){returnN;}//把t元素压入栈publicvoidpush(Tt){//找到首结点指向的第一个结点NodeoldFirsthead.next;//创建新结点NodenewNodenewNode(t,null);//让首结点指向新结点head.nextnewNode;//让新结点指向原来的第一个结点newNode.nextoldFirst;//元素个数1N;}//弹出栈顶元素publicTpop(){//找到首结点指向的第一个结点NodeoldFirsthead.next;if(oldFirstnull){returnnull;}//让首结点指向原来第一个结点的下一个结点head.nextoldFirst.next;//元素个数-1N--;returnoldFirst.item;}OverridepublicIteratorTiterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateNoden;publicSIterator(){this.nhead;}OverridepublicbooleanhasNext(){returnn.next!null;}OverridepublicObjectnext(){nn.next;returnn.item;}}}计算方法: caculate/** * param notaion 逆波兰表达式的数组表示方式 * return 逆波兰表达式的计算结果 */publicstaticintcaculate(String[]notaion){//1.定义一个栈用来存储操作数StackIntegeroprandsnewStack();//2.从左往右遍历逆波兰表达式得到每一个元素for(inti0;inotaion.length;i){Stringcurrnotaion[i];//3.判断当前元素是运算符还是操作数Integero1;Integero2;Integerresult;switch(curr){case://4.运算符从栈中弹出两个操作数完成运算运算完的结果再压入栈中o1oprands.pop();o2oprands.pop();resulto2o1;oprands.push(result);break;case-://4.运算符从栈中弹出两个操作数完成运算运算完的结果再压入栈中o1oprands.pop();o2oprands.pop();resulto2-o1;oprands.push(result);break;case*://4.运算符从栈中弹出两个操作数完成运算运算完的结果再压入栈中o1oprands.pop();o2oprands.pop();resulto2*o1;oprands.push(result);break;case/://4.运算符从栈中弹出两个操作数完成运算运算完的结果再压入栈中o1oprands.pop();o2oprands.pop();resulto2/o1;oprands.push(result);break;default://5.操作数把该操作数放入到栈中oprands.push(Integer.parseInt(curr));break;}}//6.得到栈中最后一个元素就是逆波兰表达式的结果intresultoprands.pop();returnresult;}测试:中缀表达式 3*17-1518/6逆波兰表达式 3,17,15,-,*,18,6,/,计算结果 639publicstaticvoidmain(String[]args){//中缀表达式 3*17-1518/6 的逆波兰表达式如下 639String[]notation{3,17,15,-,*,18,6,/,};intresultcaculate(notation);System.out.println(逆波兰表达式的结果为result);}