树与二叉树1-习题与解答VIP专享VIP免费

1、括号的匹配（表达式的合法性检查）[问题描述]假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。[问题分析]假设输入的字符串存储在c中（varc:string[255]）。我们可以定义一个栈：vars:array[1..maxn]ofchar;top:integer;用它来存放表达式中从左往右的左圆括号（maxn=20）。算法的思路为：顺序（从左往右）扫描表达式的每个字符c[i]，若是“（”，则让它进栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。[参考程序]programlx5;constmaxn=20;varc:string;functionjudge(c:string):boolean;vars:array[1..maxn]ofchar;top,i:integer;ch:char;beginjudge:=true;top:=0;i:=1;ch:=c[i];whilech<>'@'dobeginif(ch='(')or(ch=')')thencasechof'(':begintop:=top+1;s[top]:='('end;')':iftop>0thentop:=top-1elsebeginjudge:=false;exitend;end;i:=i+1;ch:=c[i];end;iftop<>0thenjudge:=false;end;begin{main}assign(input,'match.in');assign(output,'match.out');reset(input);rewrite(output);readln(c);ifjudge(c)thenwriteln('YES')elsewriteln('NO');close(input);close(output);end.2、编程把中缀表达式转换成后缀表达式[问题描述]输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序一致。为简单起见，假设输入的中缀表达式由＋（加）、－（减）、*（乘）、／（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即括号内部至少有一个运算符号。以下是一个运行实例233。[样例输入]X+A*（Y-B）-Z/F[样例输出]XAYB-*+ZF/-[算法设计]设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾相应地加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级；此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。上图是对范例表达式的扫描示意图。这样，我们需要事先把所有运算符号的优先级定义并存放好，这很简单，以下程序中的数组f就是用来存放运算符之间的优先级关系的。1(>)表示前面的运算符优先于后面的运算符，-1(<)表示后面的运算符优先于前面的运算符，0(=)表示前面的运算符的优先级与后面的运算符相同，2(ERROR)表示这两个运算符如果在扫描中相遇的话，意味着该表达式是错误的。需要补充的是：左括号的优先级是最高的，而里层的左括号比外层的左括号更优先，右括号的优先级是除#号以外最低的，但左括号和右括号的优先级则是相等的，这样定义的目的是为了消去括号。以上规律列表如下：+-*/（）#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=ERROR)>>>>ERROR>>#<<<<