数据结构 | 每日一练（105）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．试利用下列栈和串的基本操作完成下述填空题。 initstack(s) 置 s 为空栈； push(s,x) 元素 x 入栈; pop(s) 出栈操作; gettop(s) 返回栈顶元素； sempty(s) 判栈空函数； setnull(st) 置串 st 为空串； length(st) 返回串 st 的长度； equal(s1,s2) 判串 s1 和 s2 是否相等的函数； concat(s1,s2) 返回联接 s1 和 s2 之后的串； sub(s,i,1) 返回 s 中第 i 个字符； empty(st) 判串空函数 FUNC invert(pre:string; VAR exp:string):boolean; {若给定的表达式的前缀式 pre 正确，本过程求得和它相应的表达式 exp 并返回“true”，否则 exp为空串，并返回“false”。已知原表达式中不包含括弧，opset 为运算符的集合。} VAR s:stack; i,n:integer; succ:boolean; ch: char; BEGIN i:=1; n:=length(pre); succ:=true; (1)__; (2)__; WHILE (i<n) AND succ DO BEGIN ch:=sub（pre,i,l）; IF (3)_ THEN (4)__ ELSE IF (5)__THEN (6)_ ELSE BEGIN exp:=concat((7)___,(8)____); exp:=concat((9)___,(10)___); (11)__; END; i:=i+1 END; IF (12)___THEN BEGIN exp:=concat(exp,sub(pre,n,1)); invert:=true END ELSE BEGIN setnull(exp); invert:=false END END; 注意：每个空格只填一个语句。

正确答案

PS：||代表注释

1．(1) initstack（s） /／栈s初始化为空栈。

(2) setnull (exp) //串exp初始化为空串。 (3) ch in opset //判取出字符是否是操作符。 (4) push (s,ch) //如ch是运算符，则入运算符栈s。 (5) sempty (s) //判栈s是否为空。 (6) succ := false //若读出ch是操作数且栈为空，则按出错处理。 (7) exp (8)ch //若ch是操作数且栈非空，则形成部分中缀表达式。 (9) exp (10) gettop(s) //取栈顶操作符。 (11) pop(s) //操作符取出后，退栈。 (12) sempty(s)　//将pre的最后一个字符（操作数）加入到中缀式exp的最后。