先纪念一下，写了2小时终于AC了。

题目描述

在本题当中，你需要设法描述一个表达式的计算过程。

输入：
全称规则：Expr_all ::= Expr0 | Expr1 | Expr2
函数规则：Function ::= Func ‘(‘ Expr_all { ‘,’ Expr_all } ‘)’
元素规则：Expr0 ::= 常量 { ‘.’ Function } | ‘(‘ Expr_all ‘)’ { ‘.’ Function } | Function { ‘.’ Function }
乘法规则：Expr1 ::= Expr0 | Expr0 ‘*’ Expr1 | Expr0 ‘/’ Expr1
加法规则：Expr2 ::= Expr1 | Expr1 ‘+’ Expr2 | Expr1 ‘-‘ Expr2

优先级：
4：常量与函数
3：括号
2：点运算，左向右
1：乘除法，左向右
0：加减法，左向右

输出：
VALUE ::= 标识符 | 输出行号
加减乘除：一行OPR ‘ ‘ VALUE ‘ ‘ VALUE
函数：一行Func ‘ ‘ VALUE { ‘ ‘ VALUE }
点运算：一行Func ‘ ‘ 左值 ‘ ‘ VALUE { ‘ ‘ VALUE }

样例

(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

首先关于普通的四则运算中缀表达式，我们知道有很多方法求解，包括中缀表达式+栈(顺便转RPN)、递归下降算法、优先爬山算法。优先爬山算法是一种自底向上分析法，构造出来的语法树代表了调用的先后顺序。

所以我们可以直接进行优先爬山分析。

算法

优先爬山 $O(length)$

只遍历了一次

时间复杂度

$O(length)$

参考文献

https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/

C++ 代码

struct expr parse_primary()//处理常量、括号、普通函数。返回行号
{
    char next=getchar();
    if(next=='(')//左括号 
    {
        struct expr temp=express();
        next=getchar();//右括号
        return temp;//直接无脑弹出temp 
    }
    else//标识符。函数也在这部分
    {
        char temp=next;
        next=getchar();
        if(next=='(')//左括号 
        {
            struct expr nul;
            nul.valid=0;
            return func(temp,nul);
        }
        else//一个普通的标识符
        {
            ungetc(next,stdin);//退回左括号
            struct expr ans;
            ans.isline=0;
            ans.valid=1;
            ans.value=temp;
            return ans;
        }
    }
}

struct expr parse_opg(struct expr lhs,int cerp)//cerp是左部优先级。每次调用这个的时候，下一个总应该是运算符。点运算应该在这里特判。所有的lhs rhs代表行号
{
    char peek=getchar();//运算符1，prec是优先级
    while(peek=='.')//是个点运算
    {
        char temp=getchar();
        getchar();//左括号
        lhs=func(temp,lhs);
        peek=getchar();//再来
    }
    while(isop(peek)&&prec(peek)>=cerp)//peek是二元运算符，peek优先级大于等于左部旧优先级就要规约
    {
        char op=peek;
        struct expr rhs=parse_primary();//右部读一个并解析某个东西3
        peek=getchar();//再预读下一个运算符2。比较1和2两个运算符的优先级
        while(peek=='.')//是个点运算
        {
            char temp=getchar();
            getchar();//左括号
            rhs=func(temp,rhs);
            peek=getchar();//再来
        }
        while(isop(peek)&&prec(peek)>prec(op))//peek是二元运算符且peek优先级大于op优先级。因为赋值只能出现一次，且优先级最低，故无需考虑右结合
        {
            ungetc(peek,stdin);//这里必须退回运算符2
            rhs=parse_opg(rhs,prec(peek));//做右边
            peek=getchar();
            while(peek=='.')//是个点运算
            {
                char temp=getchar();
                getchar();//左括号
                rhs=func(temp,rhs);
                peek=getchar();//再来
            }
        }
        lhs=combine(lhs,op,rhs);//表示规约
    }
    ungetc(peek,stdin);//这里必须退一个后面的字符
    return lhs;
}