注:为了在一些编程细节上为大家带来简便，我们允许各位选择C和C++两种编程语言进行提交，可以使用C++但并不推荐，用C并没有带来更大的麻烦，而且完全可以通过。
我仰望星空， 它是那样辽阔而深邃；
那无穷的真理， 让我苦苦地求索、追随。
我仰望星空， 它是那样庄严而圣洁；
那凛然的正义， 让我充满热爱、感到敬畏。
我仰望星空， 它是那样自由而宁静；
那博大的胸怀， 让我的心灵栖息、依偎。
我仰望星空， 它是那样壮丽而光辉；
那永恒的炽热， 让我心中燃起希望的烈焰、响起春雷。
北京航空航天大学校歌，原名《仰望星空》，是2007年9月4日发表于《人民日报》文艺副刊上的一首诗歌，为当时的国务院总理温家宝所创作。
诗中所透露的对真理、正义、自由、博爱的思考，将时刻被我们所铭记着。
回到现实的学习生活中，有一个问题一直在困扰开花学长。人可以一点点推演，计算出表达式的值。但是机器在没有人脑的各种判断下，也能快速计算出表达式的值。
凡事不能知其然而不知其所以然。抱着追寻真理的热忱之情，开花学长决定与你一起走入美妙的计算机科学的世界当中，一探究竟。看一看计算机到底是怎样一点点分析，最终完成对表达式的计算的。
路漫漫其修远兮，吾将上下而求索。虽然探寻真理的道路艰难坎坷，但是相信走完这趟旅途的你，一定会有全新的收获。
本题需要用到一些C++语言的知识，但是没学过也没有关系，直接看背景介绍就好啦！
（如果对这里不熟悉的话，请不要跳过背景介绍）
在这里，我们将向大家介绍普通函数调用，结构体的成员函数和成员函数调用的概念。
在学习C语言的时候，当我们需要计算平方根的时候，我们会采用以下方式:
double a = sqrt(b); 调用math.h库函数中的sqrt函数进行运算，这就是普通函数调用。
我们在学习C语言结构体的时候，我们可以在结构体内定义成员变量
struct info {
int a;
int b;
int c;
int d;
};
struct info Information;但是在C++当中，我们还可以在结构体内部定义成员函数
struct info {
int a;
int b;
int c;
int d;
//计算两个数与其他4个成员类型变量的和
int Calc(int e, int f) {
return (a+b+c+d+e+f);
}
};
struct info Information;这样之后，如果我们要计算外部传入的两个数 $a,b$ 和该结构体内部的 $4$ 个数加和的时候，就可以写成以下形式:
printf("%d\n", Information.Calc(a, b));这样的写法在C++当中是合法的（注意不要将这种写法带入咱们平时的上机练习赛和期末考试当中哦！），这种写法即成员函数调用。
值得注意的是，表达式的计算结果不一定是单纯的数值，也可以是结构体。比如说:
struct info {
int a;
int b;
int c;
int d;
//计算两个数与其他4个成员类型变量的和
int Calc(int e, int f) {
return (a+b+c+d+e+f);
}
};
//按照某种规则构造一个info结构体
struct info generate(int a, int b) {
info ret;
info.a = a; info.b = b;
info.c = a + b; info.d = a - b;
return info;
}
int c, d;
...
int main() {
...
printf("%d\n", generate(a, b).Calc(c, d));
...
}上述的
generate(a, b).Calc(c, d)同样也是一个合法的表达式，其中 generate 函数就是一个普通函数调用，Calc函数就是一个成员函数调用。
需要注意的是，成员函数的调用是可以进行“套娃”的，因为结构体内可以继续定义结构体类型的成员变量，而每一个成员函数的返回值也可以是不同的结构体。例如：
struct A {
struct B {
struct C {
...
}
struct C calc_C(int b, int c, int d, int e) {
...
}
}
struct B calc_B(int a) {
...
}
};
struct A test_a;在上述伪代码块中，结构体A 包含成员变量结构体B以及成员函数calc_B（其返回值为结构体B），结构体B 又包含成员变量结构体C以及成员函数calc_C（其返回值为结构体C）。
那么
test_a.calc_B(a).calc_C(b,c,d,e)同样是一个合法的表达式，其计算的值为一个结构体C类型。
在C++当中，你甚至可以写一堆同名的函数，还有这种好事？还真有。
在同一个作用域内，可以声明几个功能类似的同名函数，但是这些同名函数的形式参数（指参数的个数、类型或者顺序）必须不同。不能仅通过返回类型的不同来重载函数。
举个例子，比如说math.h库当中求绝对值的函数包括:
int abs(int _X);
long labs(long _X);
long long llabs(long long _X);
double fabs(double _X);
float fabsf(float _X);
long double fabsl(long double _X);而且必须要严格按照数据类型选取对应的函数，这就很麻烦了...
但是只要合理利用函数重载，就会轻松不少。
#include<stdio.h>
int abs(int x) { return x < 0 ? -x : x; }
long abs(long x) { return x < 0 ? -x : x; }
long long abs(long long x) { return x < 0 ? -x : x; }
double abs(double x) { return x < 0 ? -x : x; }
float abs(float x) { return x < 0 ? -x : x; }
long double abs(long double x) { return x < 0 ? -x : x; }
int main() {
//do something
}这样的话，任何类型的数都可以直接调用名为abs的函数，完成绝对值的运算。
不仅可以像上面这样，完成不同参数类型的函数重载，还可以完成不同参数个数的函数重载。
#include<stdio.h>
void print(int i) {
printf("一个整数为: %d\n", i);
}
void print(double f, double g) {
printf("两个浮点数为: %f %f\n", f, g);
}
void print(char c[], char d[], char e[]) {
printf("三个字符串为 %s %s %s\n", c, d, e);
}
int main() {
//do something
}只要传入了上述声明过的任意一种参数组合形式，都可以合理得调用print函数。
一言以蔽之，在本题当中，你需要设法描述一个类C++语法的表达式的计算过程。
具体来说，你不需要求出这个表达式的具体值，你只需要描述它的计算过程，即将这个表达式分解为若干次四则运算与函数调用，且每次运算或调用的操作数都是常量或之前的运算或调用的结果。
这个表达式可能含有：
为了简化题目，我们有如下的规定：
在四则运算当中，有乘除法>加减法，同优先级从左到右运算的规则，在这里同理有:
括号>普通函数>成员函数>乘除法>加减法 普通函数与成员函数的语法成分中所包含的括号，与计算表达式中的括号并非同一性质！举例如下:
f(g)这是一个普通函数调用，但是其中出现的括号仅作为函数的语法表示成分，并不作为真正的括号参与到运算当中！
需要注意的是：运算符的优先级并不代表计算顺序的先后，在设计程序的时候，你会慢慢理解这一点。
例如，给定如下的表达式:
(a+f((b-c+e)*d/c.h(d,d)).g(e)).g(d).h(f(a,c),f(b)/f(c),f(d))这就是一个可能出现的表达式。其中：
a,b,c,d,e 是常量。f 是普通函数。g,h 是成员函数。我们用递归的方式定义合法的表达式：
[EXPR]是一个合法的表达式，那么([EXPR])（嵌套一层括号）是一个合法的表达式，其值与[EXPR]相同。[EXPR_1],[EXPR_2],……,[EXPR_n]是 $n$ 个合法的表达式（ $n$ 至少为 $1$ ），[FUNC]是一个普通函数，那么[FUNC]([EXPR_1],[EXPR_2],……,[EXPR_n])是一个合法的表达式，其值为将[EXPR_1],[EXPR_2],……,[EXPR_n]依次作为参数，调用普通函数[FUNC]所得的结果。注意同一个函数在不同的调用中可能接受不同个数的参数（详情见前面背景介绍2中所提到的函数重载的概念）。[EXPR]是一个由上述三条规则和本条规则或只由本条规则定义的一个合法的表达式，[EXPR_1],[EXPR_2],……,[EXPR_n]是 $n$ 个合法的表达式（ $n$ 至少为 $1$），[FUNC]是一个成员函数，那么[EXPR].[FUNC]([EXPR_1],[EXPR_2],……,[EXPR_n])是一个合法的表达式，其值为将[EXPR_1],[EXPR_2],……,[EXPR_n]依次作为参数，调用[EXPR]的成员函数[FUNC]所得的结果。注意同一个函数在不同的调用中可能接受不同个数的参数。（原因和上述规则相同）。[EXPR_0],[EXPR_1],……,[EXPR_n]是 $n+1$ 个上述四条规则定义的合法的表达式（ $n$ 至少为 $1$ ），[OPR_1],[OPR_2],……,[OPR_n]是 $n$ 个乘号或除号运算符，那么[EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n]是一个合法的表达式，其值为将[EXPR_0],[EXPR_1],……,[EXPR_n]依次进行[OPR_1],[OPR_2],……,[OPR_n]运算的结果。[EXPR_0],[EXPR_1],……,[EXPR_n]是 $n+1$ 个上述五条规则定义的合法的表达式（ $n$ 至少为 $1$），[OPR_1],[OPR_2],……,[OPR_n]是 $n$ 个加号或减号运算符，那么[EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n]是一个合法的表达式，其值为将[EXPR_0],[EXPR_1],……,[EXPR_n]依次进行[OPR_1],[OPR_2],……,[OPR_n]运算的结果。容易看到，这样定义的每个合法的表达式都有唯一一种解读方式，即不会引起歧义。
上述规定确定了一个表达式的值，接下来我们确定一个表达式的求值顺序。我们用与定义类似的方式规定这个顺序：
([EXPR])（括号嵌套），只需计算[EXPR]。[FUNC]([EXPR_1],[EXPR_2],……,[EXPR_n])（普通函数），先依次计算[EXPR_1]、[EXPR_2]、……、[EXPR_n]，再调用[FUNC]。[EXPR].[FUNC]([EXPR_1],[EXPR_2],……,[EXPR_n])（成员函数），先依次计算[EXPR]、[EXPR_1]、[EXPR_2]、……、[EXPR_n]，再调用[FUNC]。[EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n]（其中[OPR_1]、[OPR_2]、……、[OPR_n]全为乘除运算符），先计算[EXPR_0]，再计算[EXPR_1]，再调用[OPR_1]得出中间结果，再计算[EXPR_2]，再用上述中间结果和[EXPR_2]的结果调用[OPR_2]……直到计算完毕。[EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n]（其中[OPR_1]、[OPR_2]、……、[OPR_n]全为加减运算符），先计算[EXPR_0]，再计算[EXPR_1]，再调用[OPR_1]得出中间结果，再计算[EXPR_2]，再用上述中间结果和[EXPR_2]的结果调用[OPR_2]……直到计算完毕。可以看出，除函数外，上述运算顺序均与我们日常使用的顺序相同（即优先级更高的优先计算，同优先级的从左到右依次运算）；函数的运算顺序在不同的标准中不同，这里我们规定为函数的参数表从左至右依次运算。
输入文件只有一行，只包含一个需要处理的表达式。
表达式的长度不超过 $120$，不会出现任何空格等多余字符（也就是说，通过scanf或者getchar即可完成读入）。
按计算顺序输出每一次的运算符与函数调用。每次调用的参数只能是常量或之前某一次的运算结果，其中运算结果我们用从小到大的正整数依次表示。即：我们用单个英文字母（与输入中的相同）表示一个常量（或者普通函数调用/成员函数调用），用一个正整数表示之前某一次的运算结果，设第 $i$ 次的调用产生的结果为 $i$ 。
以下用[VALUE]表示一个参数，[OPR]表示一个运算符，[FUNC]表示一个函数，[空格]表示一个单一的空格。
如果是运算符调用（加减乘除），设这次要计算的是[VALUE_1][OPR][VALUE_2]，则你需要输出一行[OPR][空格][VALUE_1][空格][VALUE_2]。
如果是普通函数调用，设这次要计算的是[FUNC]([VALUE_1],[VALUE_2],……,[VALUE_n])，则你需要输出一行[FUNC][空格][VALUE_1][空格][VALUE_2][空格]……[空格][VALUE_n]。
如果是成员函数调用，设这次要计算的是[VALUE_0].[FUNC]([VALUE_1],[VALUE_2],……,[VALUE_n])，则你需要输出一行[FUNC][空格][VALUE_0][空格][VALUE_1][空格][VALUE_2][空格]……[空格][VALUE_n]。
值得注意的是，本题的评测方法非SPJ，而是直接进行文本比对。因为从题中不难得出，表达式的调用顺序一定是唯一的。
(a+b+c)+d+e+f+(a+a+a)+ a b
+ 1 c
+ 2 d
+ 3 e
+ 4 f
+ a a
+ 6 a
+ 5 7 这是一个只包含常量、加减号、括号的表达式，具体的运算顺序在下方的注释中有写到，每一次运算具体计算的是哪个子表达式的值
+ a b // 1 a+b
+ 1 c // 2 a+b+c
+ 2 d // 3 (a+b+c)+d
+ 3 e // 4 (a+b+c)+d+e
+ 4 f // 5 (a+b+c)+d+e+f
+ a a // 6 a+a
+ 6 a // 7 a+a+a
+ 5 7 // 8 (a+b+c)+d+e+f+(a+a+a)a+b+c+d+e*f*g*h*i*(j-k-l-m-n)+ a b
+ 1 c
+ 2 d
* e f
* 4 g
* 5 h
* 6 i
- j k
- 8 l
- 9 m
- 10 n
* 7 11
+ 3 12这是一个包含常量、四则运算符、括号的表达式，具体的解释形式同上。
+ a b // 1 a+b
+ 1 c // 2 a+b+c
+ 2 d // 3 a+b+c+d
* e f // 4 e*f
* 4 g // 5 e*f*g
* 5 h // 6 e*f*g*h
* 6 i // 7 e*f*g*h*i
- j k // 8 j-k
- 8 l // 9 j-k-l
- 9 m // 10 j-k-l-m
- 10 n // 11 j-k-l-m-n
* 7 11 // 12 e*f*g*h*i*(j-k-l-m-n)
+ 3 12 // 13 a+b+c+d+e*f*g*h*i*(j-k-l-m-n)(a+f((b-c+e)*d/c.h(d,d)).g(e)).g(d).h(f(a,c),f(b)/f(c),f(d))- b c
+ 1 e
* 2 d
h c d d
/ 3 4
f 5
g 6 e
+ a 7
g 8 d
f a c
f b
f c
/ 11 12
f d
h 9 10 13 14这是一个包含常量、四则运算符、普通函数调用、成员函数调用、括号的表达式，具体的解释形式同上。
- b c // 1 b-c
+ 1 e // 2 b-c+e
* 2 d // 3 (b-c+e)*d
h c d d // 4 c.h(d,d)
/ 3 4 // 5 (b-c+e)*d/c.h(d,d)
f 5 // 6 f((b-c+e)*d/c.h(d,d))
g 6 e // 7 f((b-c+e)*d/c.h(d,d)).g(e)
+ a 7 // 8 a+f((b-c+e)*d/c.h(d,d)).g(e)
g 8 d // 9 (a+f((b-c+e)*d/c.h(d,d)).g(e)).g(d)
f a c // 10 f(a,c)
f b // 11 f(b)
f c // 12 f(c)
/ 11 12 // 13 f(b)/f(c)
f d // 14 f(d)
h 9 10 13 14 // 15 (a+f((b-c+e)*d/c.h(d,d)).g(e)).g(d).h(f(a,c),f(b)/f(c),f(d))对于其中 $40\%$ 的数据，保证只包含常量与四则运算符、括号中的至少一种。
对于其中 $30\%$ 的数据，保证只包含常量与普通函数调用、成员函数调用、括号中的至少一种。
对于总计 $100\%$ 的数据，保证为常量、四则运算符、普通函数调用、成员函数调用、括号的各种可能组合所组成的合法表达式。
具体测试点如下:
测试点 $01, 02$ : 包含常量，加减号
测试点 $03, 04$ : 包含常量，四则运算符
测试点 $05, 06$ : 包含常量，加减号，括号
测试点 $07, 08$ : 包含常量，四则运算符，括号
测试点 $09, 10$ : 包含常量，普通函数调用
测试点 $11, 12$ : 包含常量，成员函数调用
测试点 $13, 14$ : 包含常量，普通函数调用，成员函数调用，括号
测试点 $15, 16$ : 包含常量，四则运算符，普通函数调用，括号
测试点 $17, 18$ : 包含常量，四则运算符，成员函数调用，括号
测试点 $19, 20$ : 包含常量，四则运算符，普通函数调用，成员函数调用，括号
如果觉得无从下手，推荐大家采用自顶向下递归的方式来完成表达式的解析。
以下是计算一个只有四则运算+括号的表达式的具体值的代码，可以在 表达式求值 一题内进行测试并且通过评测。
#include<stdio.h>
#include<string.h>
#include<ctype.h>
char str[114514];
int len;
//获取字符串str[l...r]之间表示的数字
int getnum(int l,int r) {
int i,ret=0;
for(i=l;i<=r;i++)
ret=ret*10+str[i]-'0';
return ret;
}
//判断字符串str[l...r]之间是否是纯数字
int isnum(int l,int r) {
int i;
for(i=l;i<=r;i++)
if(!isdigit(str[i])) return 0;
return 1;
}
//判断字符串str[l...r]的最外层括号是否互相配对
int issub(int l,int r) {
int i,in=0;
if(str[l]!='('||str[r]!=')')
return 0;
for(i=l;i<r;i++) {
in+=str[i]=='(';
in-=str[i]==')';
if(in==0)return 0;
}
return 1;
}
//获取str[l...r]当中的关键运算符，以此作为向下递归的依据
int getlst(int L,int R) {
int i,ret=-1;
int in=0;
for (i=R;i>=L;i--) {
in+=str[i]=='(';
in-=str[i]==')';
if(in!=0) continue;
//优先级 1 : 加减号 (运算顺序是从左向右，所有向下递归是从右往左寻找)
if(str[i]=='+'||str[i]=='-')
return i;
//优先级 2 : 乘除号 (运算顺序是从左向右，所有向下递归是从右往左寻找)
if((str[i]=='*'||str[i]=='/')&&ret==-1)
ret=i;
}
return ret;
}
//判断字符串str[l...r]组成的表达式的值
int c(int L,int R) {
if(L>R)
return 0;
//如果全是数字，则返回对应表达的数字
if(isnum(L,R))
return getnum(L,R);
//如果最外层括号互相匹配，则去掉最外层括号，只计算内部
if(issub(L,R))
return c(L+1,R-1);
int mid=getlst(L,R);
//获取关键的运算符，作为向下递归的依据，并分情况枚举递归情况（本代码只有加减乘除）
if(str[mid]=='+')
return c(L,mid-1)+c(mid+1,R);
if(str[mid]=='-')
return c(L,mid-1)-c(mid+1,R);
if(str[mid]=='*')
return c(L,mid-1)*c(mid+1,R);
if(str[mid]=='/')
return c(L,mid-1)/c(mid+1,R);
return 0;
}
int main() {
while(scanf("%s",str+1) != EOF)
len=strlen(str+1), printf("%d\n",c(1,len));
}上述的自顶向下递归求值运算方法，其递归函数c的回溯顺序，与本题要求的表达式求值顺序完全相同。各位同学可以根据上述代码进行改造，完成对本题的计算。
（即使不会完全归纳到普通/成员函数的调用上，仅完成四则运算与括号的部分，也可以得到 $40$ 分的成绩。）
本题除了自顶向下递归的分析方法，还可以采用自底向上递归的分析方法，感兴趣的同学可以看这个链接 ，这里就不再做详细介绍了。
p.s. 题目参考自THUPOST2016-2
Author: 计组OO两开花