Q1
```
给定一个中缀表达式，请编写程序计算该表达式的值。表达式包含+、-、*、/、^、(、)，所有运算均为二元运算，操作数均为正整数，但可能不止一位，不超过10位。运算结果为整数，值域为[−2 
31
 ,2 
31
 )。除法运算结果若为小数则进行截尾取整。若除法运算中除数为0，则输出INVALID。幂运算须自行实现，不允许调用pow等系统函数。

测试数据保证幂运算中指数为非负，底数不为0，且不会出现诸如n^a^b连续多次幂运算。

输入格式:
输入为多行，每行为一个长度不超过1000的字符串，表示中缀表达式。

输出格式:
对每个表达式输出一行：为一个整数（表达式的值）或为一个字符串INVALID。

输入样例:
5+(10*2)-6
8*(999+1)
1+5/(1-1)
7*2^3

输出样例:
19
8000
INVALID
56
代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB
栈限制
8192 KB
```

Q2
```
2021年11月6日，英雄联盟全球总决赛打响，中国电子竞技战队Edward Gaming（EDG）以3:2力克韩国强敌DWG KIA（DK）战队，历史上首次夺得全球总冠军。一时间全网沸腾，大家纷纷在社交平台上直呼“edgnb”。现给定一段文本，请编写程序识别出连续的k个“edgnb”组成的字符串在该文本中出现了多少次。

输入格式:
第一行为1个整数T，表示数据组数。对于每组数据，第一行为1个字符串，表示给定的文本。第二行为1个整数k，含义如题目所述。（1≤T≤10。各组数据给定的字符串长度之和不超过10 
5
 ，且字符串中只包含a-z的小写字母。k≥1且k×5小于给定字符串长度）。

输出格式:
对于每组数据输出一行，为1个整数，表示所求的出现次数。

输入样例:
5
xyzedgnbabcedgnb
1
xyzedgnbabcedgnb
2
defedgnbedgnbxyz
2
edgnbedgnbedgnb
2
fxedgnbedgnbedgnbedgnbmem
3

输出样例:
2
0
1
2
2

数据规模:
测试点0：5≤T≤10，400≤T个字符串长度之和≤500，k=1
测试点1：5≤T≤10，400≤T个字符串长度之和≤500，k≥1
测试点2：5≤T≤10，4000≤T个字符串长度之和≤5000，k≥1
测试点3：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1
测试点4：1≤T≤3，90000≤T个字符串长度之和≤100000，k≥1

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
```

Q3
```
波比和哈丽在玩一个字母游戏，波比给出一个字符串S，要求哈丽按照一定规则，基于该字符串算出一个数字X。

规则是：

（1）求出S的最长重复后缀P（P是S的后缀且在S中出现大于1次，例如yacbacba的最长重复后缀是acba），

（2）求出在S中去除第二长相等前后缀（S中所有相等的前后缀中第2长者，例如abcabcxxxabcabc中最长相等前后缀是abcabc，第二长的相等前后缀则是abc）后剩下的子串Q（例如abcabcxxxabcabc去除第二长相等前后缀后，剩下abcxxxabc）。

则X=P的长度+Q的长度。

注意一个字符串不能称为自己的前缀或后缀。子串Q至少为空串，其长度大于等于0，不能为负数。

请编写程序帮助哈丽根据给定字符串S，根据上述规则计算出数字X。

输入格式:
输入为若干行，每行为一个字符串，包含不超过100000个字母。

输出格式:
输出为若干行，每行一个整数，表示输入字符串所计算出的数字。 

输入样例:
abcabcxxxabcabc
xacbacba
abc
aaa

输出样例:
15
12
3
3
```