Question

任给算术表达式，试编写一个算法，输出该算术表达式的二*树结构。

任给算术表达式，试编写一个算法，输出该算术表达式的二*树结构。

例如：（a-b）*(c+d)

*

-+

abcd
需要用TASM汇编模式来做这道题～～～这是我最头痛的～～～希望高人指点～～～

Answer 1

栈运算。维护一个变量栈和一个符号栈（数字认为是变量）

符号 栈内优先级 栈外优先级
+ - 2 1
* / 4 3
^ 6 5
( 0 8
) 8 0

可以看到，优先级高的符号先算。为了方便起见，先在表达式两边加括号。
依次读入每个字符，如果是变量则入变量栈。如果是符号，就与栈顶符号比较优先级。
如果相等，则同时退栈（不处理，读下一字符）。
如果栈外大，则入栈。
如果栈内大，则以栈内符号为根，变量栈最顶2元素成为他的孩子（该2变量退栈），创建一个新的变量代表这颗以该符号为根，两变量为孩子的树。同时栈外的这个符号保留，继续与栈顶比较。

还原成树结构，取出变量栈中的最后一个元素（如果表达式合法，此时符号栈应为空，变量栈仅有1个变量），依次扩展，具体可以使用以下数据结构：

（我是学PASCAL的，不会C，所以用PASCAL语言写出来咯。。。）

type
pnode=^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处理得到的])
接着)退栈,最后边的)也和最左边的(一起退栈,此时表达式处理完毕,符号栈为空,变量栈有一个变量p2

p2记录了完整的二叉树,还原后得到了

*
- +
a b c d

总算写完了,手好酸啊,还有什么问题可以问我 QQ81727372,我是搞信息学竞赛的

Answer 2

具体算法要用到递归和二叉树中序遍历，我对这块不熟悉，手头又没有资料。
只能说说算法的大概。
像这种有括号优先的，难度较大。
Dim Ar(N) 'N：二叉树的深度
function(表达式)
｛
整个表达式从左向右读取，
有括号成对的提取出来（左侧表达式），
判断右侧近邻符号是乘除法符号则记录到二叉树
然后分别对乘除法符号进行判断
IF 成立，Then
分段split()
记录符号，再记录左右操作数
elseif 判断加减法符号 Then
Split()
End If

对表达式的右侧，递归调用本函数
直到二叉树顶结束
}

Answer 3

好象是编译原理的方式就可以解决了，楼上说得也对。通过编译原理里面对语言的分析就可以做出来，不过这可是个大工程了。

Answer 4

~~~还没有答案阿