将infix正则表达式表示法转换为后缀

Question

这是使用construction的构造算法实现有限语法正则表达式构造函数的大型程序的一小部分。在处理正则表达式之前将其转换为后缀使处理变得非常简单，因为所有内容都可以从左到右顺利读取和处理。

转换函数：

typedef struct _conv_ret {
    char *re;
    int err;
} conv_ret;

conv_ret conv(char *re) {
    /* converts limited regex infix notation with explicit
     * catenation denoted by '.' to postfix in a shunting-yard manner */
    
    conv_ret ret = {NULL, REGEX_TOOLARGE};

    if(strlen(re) > MAX_LINE)
        return ret;

    static char buf[MAX_LINE];
    char *bufp = buf;

    ret.re = buf;
    ret.err = 0;

    /* operator stack */
    int bp[strlen(re)];
    int *sp = bp; 

    #define OP_NUM 6

    /* placeholder for id 0 */
    char id_map[OP_NUM+1] = {' ', '(', '|', '.', '?', '+', '*'};
    int prec_map[OP_NUM+1] = {0, 1, 2, 3, 4, 4, 4};
    
    #define push(id) *++sp = id
    #define pop()    *bufp = id_map[*sp--]; bufp++

    for(; *re; re++) {
        /* loop skips open paren (id 1) because it is only there
         * as a placeholder until the closing paren is pushed */
        for(int id = 2; id < OP_NUM+1; id++) {
            /* pop until incoming op is 
             * highest precedence on stack */
            if(id_map[id] == *re) {
                if(sp > bp) {
                    while(prec_map[id] <= prec_map[*sp]) {
                        pop();
                    }
                }
                push(id);
                goto RELOOP;
            }
        }
        switch(*re) {
        case '(':
            push(1);
            goto RELOOP;
        case ')':
            while(*sp != 1) {
                /* couldn't find matching paren. send error */
                if(sp == bp) {
                    ret.re = NULL;
                    ret.err = PAREN_MISMATCH;
                    return ret; 
                }
                pop();
            }
            /* pop without sending paren to buf */
            --sp;
            goto RELOOP;
        default:
            /* send non op to buf */
            *bufp = *re;
            bufp++;
        }
        RELOOP: ;
    }
    /* pop all leftover values in stack to buf */
    while(sp > bp) {
        /* error if unmatched open paren */ 
        if(*sp == 1) {
            ret.re = NULL;
            ret.err = PAREN_MISMATCH;
            return ret;
        }
        pop();
    }
    
    /* null terminate */
    *bufp = 0;

    return ret;
}

头：

#include <string.h>

#define MAX_LINE 10000

/* error codes */
#define REGEX_TOOLARGE 1
#define PAREN_MISMATCH 2

注意:在程序的后期解析中会发现更多的错误，但这篇文章只是关于后缀转换的，而转换本身并不意味着要进行大量的语法和语义解析。

示例：

a+a -> aa+

a+a* -> aa+*

a.(a+b)*.b -> aab+*.b.

a.(a+b)*.b() -> aab+*.b.

a.(a+b)*.b) -> PAREN_MISMATCH

a.(a+b)*.b( -> PAREN_MISMATCH

任何旨在提高代码的效率和可读性的批评都将不胜感激。

Answer 1

一般观测

当只给出一个函数时，很难准确地定义任何瓶颈。可以看到main()和match()的短暂时刻是非常有用的，不过如果还包括match()的主体，那就更好了。

最好使用2 (1024,2048，.)的幂。对于MAX_LINE，而不是像10000这样的整数。

代码过于复杂，应该分解成多个函数，多个goto RELOOP;语句实际上证明了这一点。这些goto语句可以被break;和continue替换，在一种情况下可以替换为函数的返回。尽量避免编写意大利面码。

使用结构

实现堆栈

当可以在一个地方找到堆栈指针和堆栈容器(数组)时，维护代码就容易多了。与其将push和pop编写为宏，不如将它们实现为采用堆栈结构的函数，在push的情况下，实现它们是堆栈上正在推送的内容的参数。

幻数

虽然代码的某些部分使用符号常量而不是数字常量，但这一点可以改进，也可以使用枚举而不是#define在C中定义符号常量，我建议使用枚举来表示错误ids，因为它是可扩展的。

typedef enum Error_Code
{
    REGEX_TOOLARGE = 1,
    PAREN_MISMATCH = 2
} Error_Code;

不过，在这里，如果错误代码从0开始，而不是从1开始，那么任何错误消息都可以存储为字符串数组。

在这个代码中仍然有神奇的数字：

    int prec_map[OP_NUM] = { 1, 2, 3, 4, 4, 4 };

目前还不清楚这些数字中的任何一个是什么意思。

尚不清楚是否需要OP_NUM，因为计数可以由以下任一项确定：

    char id_map[] = { '(', '|', '.', '?', '+', '*' };
    const size_t OP_NUM = sizeof(id_map)/sizeof(*id_map);

或

    int prec_map[] = { 1, 2, 3, 4, 4, 4 };
    const size_t OP_NUM = sizeof(prec_map)/sizeof(*prec_map);

代码中的数值常数有时被称为幻数幻数，因为它们没有明显的意义。

点优化

只使用strlen()一次，并将值存储在变量中。