Monthly Archive for 六月, 2010

数据结构课设，表达式计算

Published on 2010年06月30日 in 备忘. 9 Comments Tags: , .

随便写了下，没仔细调试。

大约这么定义
double parse_expr(char *input, char **output);

input就是表达式的字符串，output是解析剩下的部分。如果output==input，就是解析失败。如果正确，返回运算结果。

用起来大约这样

    char *out, *exp="2+(1+3)*4";
    double r = parse_expr(exp, &out);
    if (out==exp){
        printf("parse fail\n");
        return 0;
    }
    printf("%s => %f \n", exp, r);

回头想下，思路跟以前写的parser几乎是葫芦画瓢，也该算是递归下降吧。

代码如下

exp.h

double parse_expr(char *input, char **output);
double parse_term(char *input, char **output);
double parse_fact(char *input, char **output);
double parse_numb(char *input, char **output);

exp.c

#include "exp.h"
 
// expr ::= term {[+-] term}
double parse_expr(char *input, char **output){
    double r=0;
    char *tmp, op;
    tmp = input;
    // factor
    r = parse_term(tmp, output);
    if (output==tmp){
        return 0;
    }
    // {[+-] term}
    tmp = *output;
    while ((op=*tmp)=='+' || op=='-'){
        double r2 = parse_term(++tmp, output);
        if (tmp==*output){
            *output = input;
            return 0;
        }
        r = (op=='+')? r+r2: r-r2;
        tmp = *output;
    }
    return r;
}
 
// term ::= factor {[*/] factor}
double parse_term(char *input, char **output){
    double r=0;
    char *tmp, op;
    tmp = input;
    // factor
    r = parse_fact(tmp, output);
    if (output==tmp){
        return 0;
    }
    // {[*/] factor}
    tmp = *output;
    while ((op=*tmp)=='*' || op=='/'){
        double r2 = parse_fact(++tmp, output);
        if (tmp==*output){
            *output = input;
            return 0;
        }
        r = (op=='*')? r*r2: r/r2;
        tmp = *output;
    }
    return r;
}
 
// fact ::= (expr) | numb
double parse_fact(char *input, char **output){
    double r=0;
    char *tmp;
    // (expr)
    if (*input=='(') {
        tmp = input+1;
        r = parse_expr(tmp, output);
        if(**output==')'){
            (*output)++;
            return r;
        }
        // if fail, output == input
        else {
            *output = input;
            return 0;
        }
    }
    // numb
    r = parse_numb(input, output);
    return r;
}
 
double parse_numb(char *input, char **output){
    double  r = 0;
    char ch, *tmp=input;
    while((ch = *tmp++)>='0' && ch<='9'){
        r = r*10+ch-'0';
    }
    *output = tmp-1;
    return r;
}

main.c

int main(){
    double r;
 
    char *out, exp[1024];
    scanf("%256s", exp);
    r = parse_expr(exp, &out);
    if (out==exp){
        printf("parse fail\n");
        return 0;
    }
    printf("%s => %f \n", exp, r);
 
    return 0;
}

无题

Published on 2010年06月28日 in 随想. 10 Comments

经常踩大街。一人出去走到哪儿是哪儿，半阴不晴的鬼天气，没有店牌的店面们没精打采的耸拉着横幅，各种喇叭不甚自信地喊着各种优惠，摆摊的人们逛街的人们钻下水道的人们上学放学的人们熙熙攘攘的人们。地方就这么大，变的都是人。

学校里各种活动…社团每年的份额。辩论赛，书画比赛，考研，考试，奖学金等等，人们总有的忙。推特上的民主人士无限精力地bs着这个当权派，新华网上依旧按部就班的各种无耻新闻。豆瓣的人们为中医是不是科学争个面红耳赤。0bug老师升级为0(7)老师然后关博。脑残不休圣战不止的圣战悄无声息地不见了声势。人们总有的忙。我呢。

目的这东西，在我意识到它不见的时候，却发现已如背叛你的一切，早已无处可寻。若是空虚得紧，就是什么函数式什么内核也无济于事。“不过走下去自然有路。”我这么安慰自己，甚至不知道自己信还是不信。“走下去自然有路。”如此，走遍了这座小城。走过了曾经不减肥的五月和这个徒伤悲的六月。

—-

昨晚在大路兄宿舍阳台上，看楼下的辅导员和警车。第二天封楼。

“咱们学校倒也还不错的。”
“建设的很好，不过上面是一群官僚。”

对付学生，上面经验的很。扣下学生一张证件，若哪个宿舍有酒瓶暖瓶之类的杂物掉下，楼下的辅导员定位出来就扣下整个宿舍的证件。也得警车来来回回威慑，要诀就是防患于未然，要是学生都闹起来扣毕业证就不好使了。

保卫科的小面包上面放一个小灯，跟警车一起来来回回的转。辅导员不停地拍着蚊子。身在这个官僚体系最底层的人们如此兢兢业业…真是个神奇的世界。

过两个月，迎接新生又会是什么图景！

我就想，我们认认真真生活的这个世界，又有多少是别人认认真真装出来的？

这可是四年的地方，谁舍得。

—-

没找着某佳的宿舍，给某鹏和飞哥打电话也没通。突然就难过的很，这些人说不见就不见了不成！

过会儿飞哥打电话回来，刚才在收拾东西。还好还好，还能打个电话。

有段时间飞哥忙着写书，经常能见面，见面就去北门吃饭。“在餐厅吃也方便，不过得多走走。”飞哥，zneil等等几人一伙，必点西红柿炒鸡蛋。

有次回来飞哥问喜不喜欢看水浒。“我最佩服林冲，太能忍了。当年统领八十万禁军啊…光忍不行，也得能怒，你看风雪山神庙…这就是大侠！”

这人混过学生会，干过程序，写过书，考过研，搞过机器人。说不累是假的。

去年一个莫名其妙的饭局上，发现飞哥不见了。出来找，见他一人在外面。“我爸刚才给我电话，没敢接怕他听出来喝酒。。。走，出去透口气。”

问我“你有什么打算？”

不知道…不考研反正…不敢想以后…

然后坐在马路牙子上，吐酸水。“你知道我为什么理平头？掉头发。前几天去拿药，医生说我胃分泌的有点乱。。”

“千千万万在大四前解决感情问题。。做这机器人耽误了暑假的两个月，考研的黄金时期。。”

一会儿回去，仍是同样的谈笑风生，跟社会上的那帮人闹的不亦乐乎，整个桌子依然围着他转。你保准看不出一丝破绽。

。。。

如今能说的只剩下保重，后会有期。

—–

把zneil叫出来吃饭，这人神奇的课表剩下整整一年完全没课，再没考研的打算，整个人都宅了。

这帮混蛋整的都是什么事情！不甘心…可我们有什么办法？No body cares，所以认真你就输了。

无能为力，这就叫一败涂地。

还是老老实实的，搞好自己吧。

—–

《了不起的盖茨比》里面印象最深的是这么一段：

“他们都是一帮混蛋，”我隔着草坪喊道：“把他们加在一起都比不上你！”

我后来一直很高兴我说了那句话。那是我对他说过的唯一一句恭维话。因为我自始至终都不认同他。

—–

“干死英格兰！”

对面楼上喊，不过灯已经黑了一半。辅导员应该结束了几天的辛苦，可以睡个安稳觉了。

他们会在什么地方看球！

GCC内联汇编的笔记

Published on 2010年06月10日 in 笔记. 2 Comments Tags: , .

起比VC风格的内联汇编，GCC的确实要别扭些，一开始要不看手册肯定一头雾水。

int foo = 10, bar = 15;
asm volatile("addl  %%ebx,%%eax"
            :"=a"(foo)                //output constraint
            :"a"(foo), "b"(bar)      //input constraint
            :                            //clobbered registers(ignored)
);

指令大家都明白，不过:”=a”(foo)这样的语法就古怪了。:后面的东西好像叫做约束，指明了输出和输入中用到的变量和寄存器。第一个的”=a”(foo)是输出的约束，就表示汇编执行完毕后foo=a。后面的”a”(foo)是输入的约束，表示汇编执行前的a=foo。这一来C和汇编就可以在约束下边交换数据了。

刚才这个a就是表示分配eax寄存器。

各种约束还挺多的…

a,b,c,d 对应eax,ebx,ecx,edx
S,D 对应esi,edi
I 常数
q eax,ebx,ecx,edx中静态分配一个
r eax,ebx,ecx,edx,esi,edi中静态分配一个
m 内存定位
A 同时分配eax和ebx，形成一64位的寄存器
i 一个编译时确定的立即数。好像ljmp指令的第一个参数就必须得是立即数，比如ljmp $0×80, $label。如果ljmp ax, $label就绘出现一个“Error: suffix or operands invalid for ‘ljmp’的错误”

为什么要这么难看的语法呢…我猜这东西最早应该是给编译器而不是给人类设计的吧，比起VC风格的内联汇编，它可以得到更多关于变量和寄存器的信息，编译器分配起寄存器来可以心里有数，不用怕自作聪明的人类把事情都搞乱掉。