栈运算。维护一个变量栈和一个符号栈（数字认为是变量）符号栈内优先级 栈外优先级+ - 2 1* / 4 3 ^
6 5(
0 8)
8 0可以看到，优先级高的符号先算。为了方便起见，先在表达式两边加括号。依次读入每个字符，如果是变量则入变量栈。如果是符号，就与栈顶符号比较优先级。如果相等，则同时退栈（不处理，读下一字符）。如果栈外大，则入栈。如果栈内大，则以栈内符号为根，变量栈最顶2元素成为他的孩子（该2变量退栈），创建一个新的变量代表这颗以该符号为根，两变量为孩子的树。同时栈外的这个符号保留，继续与栈顶比较。还原成树结构，取出变量栈中的最后一个元素（如果表达式合法，此时符号栈应为空，变量栈仅有1个变量），依次扩展，具体可以使用以下数据结构：（我是学PASCAL的，不会C，所以用PASCAL语言写出来咯。。。）typepnode=^node;node=record
leftchild,rightchild:pnode;
va:string
end;其中va域表示子树根里面记载的变量，leftchild和rightchild指向左子树和右子树。以你给的(a-b)*(c+d)为例左右先加括号变成((a-b)*(c+d))读入(,(,a,-,b,),*,(,c,+,d,),)时进行了如下操作(入栈,(入栈,a入栈,-入栈[-比(优先级大],b入栈,)处理时,因为)优先级比-小,取出a,b,-,创建变量p入变量栈,p(va='-',^leftchild.va='a',^rightchild.va='b').继续处理),此时栈外)与栈内(优先级相等,同时退栈,继续,*入栈,(入栈,c入栈................................直到)处理完c+d后,处理*,创建变量p2,p2(va='*',leftchild=p,rightchild=p1[p1是c+d处理得到的])接着)退栈,最后边的)也和最左边的(一起退栈,此时表达式处理完毕,符号栈为空,变量栈有一个变量p2p2记录了完整的二叉树,还原后得到了
*- + a b c d总算写完了,手好酸啊,还有什么问题可以问我 QQ81727372,我是搞信息学竞赛的 |
