使用递归向下法求解字符串计算式
星期一, 五月 10th, 2010
最近听了《软件构造》课上郑涛老师讲的编译原理，受益颇丰，仅管有很多地方没听懂~~印象最深的就是讲自顶向下解析上下文无关文法时，涛哥用3重递归，在不使用Stack的情况下，以极为简洁优雅的代码实现了简单的四则运算式子的计算。记得当时全班震惊，叹为观止，要知道之前学数据结构时，大家为实现这个计算，得使用Stack，而且代码繁多。那节课下来，我才发现，原来编译原理还是很有必要学习的。鉴于涛哥课上写的只支持乘法和加法，没有sin一类的函数，数字也只能是一位数，为了巩固那节课的知识，我后来自己想了想，实现了一个基本是全功能的计算器，支持+、-、*、/、^(乘方)，sin、cos等，以及PI等常数（其实说穿了，所谓的“全功能”，只是一个嚼头，真正的精华，只在于涛哥那简单的3重递归的自顶向下解析的思想）。程序的文法推理如下：
E -> T1 E’
E’ -> + T1 E’ | -T1 E’ |ε
T1 -> T2 T1′
T1′ -> * T2 T1′ | / T2 T1′ | ε
T2 -> T3 T2′
T2′ -> ^T3 T2′ |ε
T3 -> CF|F
F -> (E)|num|CONST
C-> sin|cos|tan
CONST -> PI|E|G
实现的思路是，对每个非终结符，对应一个函数，通过这些函数相互递归，实现字符串的解析和表达式的求解。为了提高效率，对于带撇号非终结符，可以用While循环代替。程序使用c++实现，代码如下:
//递归向下法求解字符串计算式
//author abraham
//email abeyuhang@gmail.com|abraham1@163.com
//blog http://blog.yuhanghome.net
//website http://yuhanghome.net
#include<iostream>
using namespace std;
char buffer[200];
const double PI=3.151592654;
const double E=2.68;
int cur_pos=0;
char cur_char;
double _e();
double _t1();
double _t2();
double _t3();
double _f();
void _c(char* cmd);
double _fun(const char* cmd,double param);
double _double();
double _const();
bool isDigit(const char c){
if(c>='0' && c<='9')
return true;
else return false;
}
char read_next(){
cur_char=buffer[cur_pos];
cur_pos++;
return cur_char;
}
void error(const char* p){
cout<<p<<"(error at "<<cur_pos<<", when char is \'"<<cur_char<<"\')"<<endl;
getchar();
getchar();
exit(-1);
}
double _const(){
double val=0;
switch(cur_char){
case 'P':
if(read_next()=='I'){
val = PI;
}else{
error("未识别的常量");
}
break;
case 'E':
val = E;
break;
default :
error("未识别的常量");
break;
}
read_next();
return val;
}
double _double(){
bool found_dot=false;
double shift=10.0;
double val=0.0;
while(true){
if(isDigit(cur_char)==1){
if(!found_dot){
val=val*10+cur_char-'0';
}else{
val+=(cur_char-'0')/shift;
shift*=10.0;
}
}else if(cur_char=='.'){
if(!found_dot){
found_dot=true;
}else error("错误的数字格式");
}else break;
read_next();
if(cur_char==0){
break;
}
}
return val;
}
double _calc(const char op,double param1,double param2){
switch(op){
case '+':
return param1+param2;
case '-':
return param1-param2;
case '*':
return param1*param2;
case '/':
case '\\':
return param1/param2;
default:
error("错误的运算符!");
}
return 0;
}
double _e(){
double val=_t1();
char op=0;
while(cur_char=='+' || cur_char=='-' ){
op=cur_char;
read_next();
val=_calc(op,val,_t1());
}
return val;
}
double _t1(){
double val=_t2();
char op=0;
while(cur_char=='*' || cur_char=='/' || cur_char=='\\'){
op=cur_char;
read_next();
val=_calc(op,val,_t2());
}
return val;
}
double _t2(){
double val=_t3();
while(cur_char=='^'){
read_next();
val=pow(val,_t3());
}
return val;
}
void _c(char * cmd){
int i=0;
while(true){
if( cur_char>='a' && cur_char<='z'){
cmd[i]=cur_char;
i++;
read_next();
}
else{
cmd[i]=0;
break;
}
}
}
double _fun(const char* cmd,double param){
double val=0;
if(strcmp(cmd,"sin")==0){
val=sin(param);
}else if(strcmp(cmd,"cos")==0){
val=cos(param);
}else if(strcmp(cmd,"tan")==0){
val=tan(param);
}else error("Bad function!");
return val;
}
double _t3(){
double val=0;
char cmd[5];
double f=0;
switch(cur_char){
case 's':
case 'c':
case 't':
_c(cmd);
f=_f();
val=_fun(cmd,f);
break;
default:
val=_f();
break;
}
return val;
}
double _f(){
double val=0;
switch(cur_char){
case '(':
read_next();
val=_e();
if(cur_char!=')')
error("括号不匹配!");
read_next();
break;
case 'P':
case 'E':
val=_const();
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
val=_double();
break;
default:
error("不能识别的符号。");
}
return val;
}
void main(){
while(true){
cur_pos=0;
cout<<"请输入一个运算表达式(q to quit):"<<endl;
cin>>buffer;
read_next();
if(cur_char=='q'){
cout<<"Good Bye!"<<endl;
break;
}
double ans=_e();
if(cur_char==0)
cout<<"答案:\t"<<ans<<endl<<endl;
else{
error("表达式出现异常结尾！");
}
}
}
后来又把代码改成了JavaScript版本的，为了方便在网页展示~~
(三角函数使用弧度)代码请查看本篇章的html源码中的 http://blog.yuhanghome.net/javascript/calc.js
