线性表--06---栈---常见应用场景

括号匹配问题

问题描述:

分析：

1. 创建一个栈用来存储左括号
2. 从左往右遍历字符串，拿到每一个字符
3. 判断该字符是不是左括号，如果是，放入栈中存储
4. 判断该字符是不是右括号，如果不是，继续下一次循环
5. 如果该字符是右括号，则从栈中弹出一个元素t；
6. 判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号
7. 循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配
   
   
   

代码实现：

栈 Stack:

importjava.util.Iterator;publicclassStack<T>implementsIterable<T>{//记录首结点privateNodehead;//栈中元素的个数privateintN;privateclassNode{publicTitem;publicNodenext;publicNode(Titem,Nodenext){this.item=item;this.next=next;}}publicStack(){this.head=newNode(null,null);this.N=0;}//判断当前栈中元素个数是否为0publicbooleanisEmpty(){returnN==0;}//获取栈中元素的个数publicintsize(){returnN;}//把t元素压入栈publicvoidpush(Tt){//找到首结点指向的第一个结点NodeoldFirst=head.next;//创建新结点NodenewNode=newNode(t,null);//让首结点指向新结点head.next=newNode;//让新结点指向原来的第一个结点newNode.next=oldFirst;//元素个数+1；N++;}//弹出栈顶元素publicTpop(){//找到首结点指向的第一个结点NodeoldFirst=head.next;if(oldFirst==null){returnnull;}//让首结点指向原来第一个结点的下一个结点head.next=oldFirst.next;//元素个数-1；N--;returnoldFirst.item;}@OverridepublicIterator<T>iterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateNoden;publicSIterator(){this.n=head;}@OverridepublicbooleanhasNext(){returnn.next!=null;}@OverridepublicObjectnext(){n=n.next;returnn.item;}}}

匹配方法 isMatch():

/** * 判断str中的括号是否匹配 * @param str 括号组成的字符串 * @return 如果匹配，返回true，如果不匹配，返回false */publicstaticbooleanisMatch(Stringstr){//1.创建栈对象，用来存储左括号Stack<String>chars=newStack<>();//2.从左往右遍历字符串for(inti=0;i<str.length();i++){StringcurrChar=str.charAt(i)+"";//3.判断当前字符是否为左括号，如果是，则把字符放入到栈中if(currChar.equals("(")){chars.push(currChar);}elseif(currChar.equals(")")){//4.继续判断当前字符是否是有括号，如果是，则从栈中弹出一个左括号，并判断弹出的结果是否为null,如果为null证明没有匹配的左括号，如果不为null，则证明有匹配的左括号Stringpop=chars.pop();if(pop==null){returnfalse;}}}//5.判断栈中还有没有剩余的左括号，如果有，则证明括号不匹配if(chars.size()==0){returntrue;}else{returnfalse;}}

测试:

publicstaticvoidmain(String[]args){Stringstr="上海(长安)())";booleanmatch=isMatch(str);System.out.println(str+"中的括号是否匹配："+match);}

逆波兰表达式求值问题

• 逆波兰表达式求值问题是我们计算机中经常遇到的一类问题，要研究明白这个问题，首先我们得搞清楚什么是逆波兰表达式？要搞清楚逆波兰表达式，我们得从中缀表达式说起。

中缀表达式：

• 中缀表达式就是我们平常生活中使用的表达式，例如：1+3*2,2-(1+3)等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。
• 中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。

逆波兰表达式(后缀表达式)：

• 逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。
  

需求：

• 给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果。
  

分析：

代码实现：

栈 Stack:

importjava.util.Iterator;publicclassStack<T>implementsIterable<T>{//记录首结点privateNodehead;//栈中元素的个数privateintN;privateclassNode{publicTitem;publicNodenext;publicNode(Titem,Nodenext){this.item=item;this.next=next;}}publicStack(){this.head=newNode(null,null);this.N=0;}//判断当前栈中元素个数是否为0publicbooleanisEmpty(){returnN==0;}//获取栈中元素的个数publicintsize(){returnN;}//把t元素压入栈publicvoidpush(Tt){//找到首结点指向的第一个结点NodeoldFirst=head.next;//创建新结点NodenewNode=newNode(t,null);//让首结点指向新结点head.next=newNode;//让新结点指向原来的第一个结点newNode.next=oldFirst;//元素个数+1；N++;}//弹出栈顶元素publicTpop(){//找到首结点指向的第一个结点NodeoldFirst=head.next;if(oldFirst==null){returnnull;}//让首结点指向原来第一个结点的下一个结点head.next=oldFirst.next;//元素个数-1；N--;returnoldFirst.item;}@OverridepublicIterator<T>iterator(){returnnewSIterator();}privateclassSIteratorimplementsIterator{privateNoden;publicSIterator(){this.n=head;}@OverridepublicbooleanhasNext(){returnn.next!=null;}@OverridepublicObjectnext(){n=n.next;returnn.item;}}}

计算方法: caculate

/** * @param notaion 逆波兰表达式的数组表示方式 * @return 逆波兰表达式的计算结果 */publicstaticintcaculate(String[]notaion){//1.定义一个栈，用来存储操作数Stack<Integer>oprands=newStack<>();//2.从左往右遍历逆波兰表达式，得到每一个元素for(inti=0;i<notaion.length;i++){Stringcurr=notaion[i];//3.判断当前元素是运算符还是操作数Integero1;Integero2;Integerresult;switch(curr){case"+"://4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中o1=oprands.pop();o2=oprands.pop();result=o2+o1;oprands.push(result);break;case"-"://4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中o1=oprands.pop();o2=oprands.pop();result=o2-o1;oprands.push(result);break;case"*"://4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中o1=oprands.pop();o2=oprands.pop();result=o2*o1;oprands.push(result);break;case"/"://4.运算符，从栈中弹出两个操作数，完成运算，运算完的结果再压入栈中o1=oprands.pop();o2=oprands.pop();result=o2/o1;oprands.push(result);break;default://5.操作数，把该操作数放入到栈中；oprands.push(Integer.parseInt(curr));break;}}//6.得到栈中最后一个元素，就是逆波兰表达式的结果intresult=oprands.pop();returnresult;}

测试:

• 中缀表达式 3*（17-15）+18/6
• 逆波兰表达式 3,17,15,-,*,18,6,/,+
• 计算结果 6+3=9

publicstaticvoidmain(String[]args){//中缀表达式 3*（17-15）+18/6 的逆波兰表达式如下 6+3=9String[]notation={"3","17","15","-","*","18","6","/","+"};intresult=caculate(notation);System.out.println("逆波兰表达式的结果为："+result);}