-
Notifications
You must be signed in to change notification settings - Fork 1
/
P165.h
48 lines (37 loc) · 1.67 KB
/
P165.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**************************************************
@Author: Jie Feng
@Time: 2018/10/13 14:29
@File: P165.h
@Description: The third week's assignment of data structure of Mr. Jianhua Lv
**************************************************/
#pragma once
/*
以下对应于英文书上 P165 1
答:
1)A*B*C 的后缀表达式为:AB*C*
2)-A+B-C+D 的后缀表达式为:-AB+C-D+
3)A*-B+C 的后缀表达式为:A-B*C+
4)(A+B)*D+E/(F+A*D)+C 的后缀表达式为:AB+D*EFAD*+/+C+
5)A && B||C||!(E>F) 的后缀表达式为:AB&&C||EF>!||
6)!(A && !( (B<C) || (C>D) ) )||(C<E) 的后缀表达式为:ABC<CD>||!&&!CE<||
*/
/*
以下对应于英文书上 P165 2
答:
1)如果含有n个操作符和分界符,假设对于操作符总共定义了 k 个优先级,那么可以分为两种情况:
a、n <= k
对于这种情况,那么栈中可能的最大元素的个数为 n ,即不存在分界符、n 个操作符的
优先级均不相同、n 个操作符入栈顺序按照优先级降序排列,只有在满足这3个条件时,
才可能在操作符全部入栈之前不因为优先级而导致退栈操作,从而达到最大的栈内元素个数
b、n > k
对于这种情况,那么栈中可能的最大元素个数为 k 个,且需要满足:操作数个数大于 k、
操作数优先级遍布 k 个优先级、操作数入栈顺序按照优先级降序排列,满足这3个条件,
才可能在操作符全部入栈之前不因为优先级而导致退栈操作(同一类优先级进行退栈是允许的),
从而达到最大的栈内元素个数
2)如果含有 n 个操作符,括号嵌套的深度最大为6
六层括号嵌套形如:( ( ( ( ( (a+b)*a+b )*a + b)*a + b)*a + b)*a + b)*a + b
上面是最简单的、所用操作符个数最少的嵌套形式,用了 11 个操作符,其中在碰到结束符'#'前
最后一个操作符会留在栈中,其余10个操作符全部出栈了,在此基础上考虑,按照上面的思想则
可以得出,栈中可能的最大元素个数为 k 个(在 n - 10 > k,且需满足第一问中的b情况的三个条件),
或者可能为 n -10 个(在 n -10 <= k,且需满足第一问的a情况的三个条件)
*/