上下文无关文法处理简单的数学表达式
先上代码
<![CDATA[
/*
* main.cpp
*
* Created on: 2014-5-27
* Author: Administrator
*/
#include <stdlib.h>
#include <iostream>
using namespace std;
struct token {
char kind;
double value;
};
//返回一个token，kind类型可能为：+、-、*、/、d（代表double类型）、o（表达式结束）
//主要分为三个类型，1.运算对象d 2.运算符+、-、*、/、(、) 3.表达式结束o
void get_token(struct token* tok);
//放回一个token，不包括d类型的token
void put_token(struct token tok);
//计算一个expression
double expression();
//计算一个term
double term();
//计算一个primary
double primary();
/*---------------------------------------------------------*/
int main() {
cout << "start" << endl;
double cal; //表达式结果
cout << "输入表达式，回车结束。" << endl
<< "注意：" << endl
<< "1.仅支持+、-、*、/操作，*不能省略，只识别(),不识别[]." << endl
<< "2.要求回车之前有\"=\",代表表达式结束!" << endl
<< "比如1+(2*3+4*(5+6))/50="<< endl;
cout << endl
<< "开始输入表达式：";
cal = expression();
cout << "计算结果：" << cal << endl;
cout << "end" << endl;
system("pause");
return 0;
}
/*---------------------------------------------------------*/
void get_token(struct token* tok) {
cin.get(tok->kind);
switch (tok->kind) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
cin.putback(tok->kind);
cin >> tok->value;
tok->kind = 'd'; //设置kind类型为d
return;
case '+':
case '-':
case '*':
case '/':
case '(':
case ')': //如果获得的是运算符，函数结束
return;
default: //得到非运算对象、运算符，比如=、NULL（没有获取到字符），代表表达式结束
tok->kind = 'o'; //over
return;
}
}
void put_token(struct token tok) {
//因为不包括d类型，所以可以直接putback，否则还要value转换为string类型
cin.putback(tok.kind);
}
double expression() {
double left = term();
struct token tok;
get_token(&tok);
while (true) {
switch (tok.kind) {
case '+':
left += term();
get_token(&tok);
break;
case '-':
left -= term();
get_token(&tok);
break;
case 'o': //表达式结束,并不需要放回token
return left;
default:
//获得了子表达式的一部分。假如表达式为1+(2*3)=,
//primary遇到“(”就会把(2*3)当做子表达式,
//所以expression要放回字表达式的部分
put_token(tok);
return left;
}
}
}
double term() {
double left = primary();
struct token tok;
get_token(&tok);
while (true) {
switch (tok.kind) {
case '*':
left *= primary();
get_token(&tok);
break;
case '/':
left /= primary();
get_token(&tok);
break;
default: //总之是获得了非*、/，代表term结束，所以要放回tok
put_token(tok);
return left;
}
}
}
double primary() {
double value;
struct token tok;
get_token(&tok);
switch (tok.kind) {
case '(':
value = expression();
get_token(&tok); //去掉与之前匹配的")"
return value;
case 'd':
return tok.value;
}
}
]]>
注意程序中需要注意的几点：
- 每一层的结束条件是获得了其它层的token或者显示的o型token，获得其它层的token要放回去，而显示的o型token，并不用放回。比如expression层
- ()看作是primary层
- 严格的上下文无关文法只是识别一个表达式，并不需要计算，也就是说只需要判断()是否匹配（当然获得的其他token是合法的表达式部分）。而本程序要求表达式正确才能计算，否则未知。
- 在用上下文无关文法处理问题时，难处在于获得正确的文法，然后再说程序实现。
列表
上一篇
下一篇