表达式求值(随心所欲版)
一、构建 tokens
所有的代码基本上都在 sdb.c中实现,没有轮子自己造。
构建 tokens 这步,基本上就是实现一个简单的词法分析器,从 args[0]开始,一个一个模式进行识别。比如对于表达式:
- 0x80100000+ ($a0 +5)*4 - ( $ t1 + 8) + 32
首先就要能识别出 0x开头的 16进制数、$开头的寄存器,识别出来以后,我们首先就是把这些能计算的都先计算,然后转化为 10 进制数的字符串,做成 token,存到 tokens 中。因此首先需要一个辅助函数:
1 |
|
这个函数能根据寄存器的名字,返回寄存器的值。
接着就可以分析了:
1 |
|
看起来很简单,接下来 make_token():
1 |
|
make_token 的关键点在于,如果一个 pattern 是以 0 开始的,那么它一定是一个 16 进制数;如果是以 $ 开始的,那么它一定是一个寄存器。这就有了关键的计算:
1 |
|
这里面处理的时候,将所有的值都是按照无符号保存的。
这时候,就可以认为,tokens 已经大功告成了!
二、中缀转后缀
这个需要造一点轮子:
1 |
|
还需要确定 token 类型:
1 |
|
还要比较优先级:
1 |
|
接着就可以中缀转后缀了:
1 |
|
思路就是,如果它是一个数,就存到 post 中;如果是一个左括号,就进栈;如果是一个右括号,就退栈,一直退到左括号,并且将这些元素送到 post 中,然后弹出左括号;如果是一个运算符,这时候就得比较运算符的优先级了:
- 如果token 优先级小于等于栈顶元素,那么就退栈,存到 post 中,一直到优先级大于栈顶;
- 然后将 token 进栈;
最后,再将栈中所有元素 pop,并存到 post中。
以上就是中缀表达式转后缀表达式的过程。
有了后缀表达式后,就可以轻松的计算了:
1 |
|
同样,这个计算过程也需要用到栈,不在累赘。
然后完善接口:
1 |
|
然后就可以计算了:
1 |
|
总之,除了解引用都可以完成任务。
三、测试
如果一个一个测试将会非常麻烦,我们利用编程语言天然地计算中缀表达式,将这个结果和我们的计算结果进行比较,如果一样,就输出 passed!。那么如何获取中缀表达式呢?可以写一个程序,让它自己生成。
程序 gen-expr.c 就实现了这样的功能:
1 |
|
我为了防止它递归太深,就用参数进行了限制;至于中途产生的除以 0 行为,我直接禁掉了,原因很简单:
- 如果+、-、* 都没问题,那么说明算法没有问题;
- 如果一个表达式长度适中可以计算,那么长得表达式一定也可以计算,如果不能,只需要扩大 buf;
- 这是在进行算法正确性验证,因此有理由这样做。
接着,生成了如下的值:表达式后:
1 |
|
直接在 cmd_p()中进行验证:
1 |
|
结果如下:
1 |
|
100 个表达式全部通过,因此可以认为表达式求值没有问题。
四、总结
以上的做法比较复杂,因此我打算利用系统提供的模板,用递归求值、正则匹配等重新做一遍。