JavaEE习题3.ppt

* * 题3.17 题3.19 题3.22 题3.28 题3.31 题3.21 题3.19 假设一个算术表达式中可以包含三种符号；圆括号“（”和“）”、方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写判别给定表达式所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。 题3.19 int matching(SqList exp) { // 顺序表exp中存有数据元素为字符的表达式, // 若表达式中三种括弧正确嵌套，则返回 1, // 否则返回 0。 } i = 1; InitStack(S); while (i=exp.length) { } if (StackEmpty(S)) return 1; else return 0; ……(下一页) switch (exp.elem[i++]) { case ?(? : case ?[? : case ?{? : {Push(S, exp.elem[i]); break;} case ?)?: { if (!StackEmpty(S)){ Pop(S,e); if (e!=?(?) return 0;} else return 0; break; } case ?]?: { if (!StackEmpty(S)){ Pop(S,e); if (e!=?[?) return 0;} else return 0; break; } case ?}?: { if (!StackEmpty(S)){ Pop(S,e); if (e!=?{?) return 0;} else return 0; break; } } 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1序列2’模式的字符序列。 其中序列1和序列2中不包含字符’’，且序列2是序列1的逆序列。例如，‘a+bb+a’是属于该模式的字符序列，而‘1+22-1’则不是。 题3.17 则这个算法和“判别括弧是否正确匹配”的算法极其相似。 同样，在算法过程中需要用到一个栈，由于序列中必定出现字符? ?， 则可将在字符??出现之前的所有字符均入栈，滤去字符??之后再读入的字符则应和栈顶的字符相等，当然，首先必须判别此时的“栈”是否为“空栈”。 此题的参数仅为一个字符序列，可以设为元素为字符的数组。 int symmetry() { } InitStack(s); e=getchar()； if (e!=‘@’){ //非结束 while(e!=‘’) //‘’前入栈 {??push(s,e);e=getchar()；} while((e=getchar())!=‘@’)//开始比对 ? { if(StackEmpty(s)) return 0;???? pop(s,c); //匹配出栈 ???? if(e!=c) return 0;?? }??if(!StackEmpty(s)) return 0;??return 1; //栈空-匹配 } else return 1; 从中缀表达式e1求得后缀式e2的规律为： 设操作符栈为S，初始为空栈，压入‘#’。 对中缀表达式从左向右扫描， 如操作数直接写入e2， 若是操作符（记为w），分情况1-4处理， 直至表达式e1扫描完毕。 1）w为一般操作符，与栈顶操作符比较优先级， 若w优先级高于栈顶操作符，则入栈； 否则栈顶操作符出栈到e2， w再与新栈顶操作符进行上述比较，直至w入栈。 题3.21 从中缀表达式exp1求得后缀式exp2的规律为： 2）w为左括号‘（’，直接入栈。 3）w为右括号‘）’： 操作符栈退栈并进入e2，直到遇到左括号为止， 然后左括号出栈，继续读e1的下一字符。 4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到e2，直至遇到‘#’，退栈，整个操作结束。 中缀表达式8-(3+5)*(5-6/2) 的