| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2999 人关注过本帖
标题:[分享]使用确定式有限状态机(DFA)及语法树(Syntax tree)实现简单的表达 ...
只看楼主 加入收藏
yuki
Rank: 2
等 级:新手上路
威 望:5
帖 子:508
专家分:0
注 册:2005-2-4
收藏
 问题点数:0 回复次数:10 
[分享]使用确定式有限状态机(DFA)及语法树(Syntax tree)实现简单的表达式求值

这里仅提供代码供大家参考学习,并希望的到大家的意见与建议。

expr.h文件

#ifndef _EXPR_H_
#define _EXPR_H_

typedef enum {
STATE_DIGIT, // digits
STATE_OPERATOR, // operators
STATE_RPAREN, // symbolic ')'
STATE_BLANK, // space and tab
STATE_DELIMITER, // symbolic '|'
STATE_UNKNOWN // unrecognized symbolic
} state_e;

typedef enum {
NTYPE_VALUE,
NTYPE_OP
} ntype_e;

typedef struct tagSyntaxTreeNode {
ntype_e t; // node type
union {
char op; // operator;
float value; // value contain in this node
} u;
struct tagSyntaxTreeNode *lchild;
struct tagSyntaxTreeNode *rchild;
} ATTR_SYNTAX_TREE_NODE;

int mid2pos( char mid_e[], char pos_e[] );
float calc_expr( char mid_e[] );
float calc_expr2( ATTR_SYNTAX_TREE_NODE *p_root );

ATTR_SYNTAX_TREE_NODE *create_syntax_tree( char pos_e[] );

void delete_syntax_tree( ATTR_SYNTAX_TREE_NODE *p_root );

#endif

expr.c文件

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "expr.h"

static int prio( char op )
{
switch( op )
{
case '+' : case '-': return 1;
case '*' : case '/': return 2;
case '(' : return -1;
default:
return -1;
}
}

static int isop( char op )
{
switch( op )
{
case '+':
case '-':
case '*':
case '/':
case '(':
return 0;
default:
return 1;
}
}

static int isdigit( char c )
{
if( c >= '0' && c <= '9' )
return 0;
return 1;
}

static float calc( float opr1, float opr2, char op )
{
switch( op )
{
case '+': return opr1+opr2;
case '-': return opr1-opr2;
case '*': return opr1*opr2;
case '/': assert(opr2); return opr1/opr2;
}
}

int mid2pos( char mid_e[], char pos_e[] )
{
char op_stack[80];

int top = -1;
int i = 0, j = 0;

state_e s = STATE_UNKNOWN;

while( mid_e[i] != '\0' )
{
if( !isdigit(mid_e[i]) )
s = STATE_DIGIT;
else if( !isop(mid_e[i]) )
{
if( s == STATE_DIGIT )
pos_e[j++] = '|';
else if( s == STATE_OPERATOR && mid_e[i] != '(' )
{
printf("Unrecoginzed operator %c%c\n", mid_e[i-1], mid_e[i]);
return 1;
}
s = STATE_OPERATOR;
}
else if( mid_e[i] == ')' )
s = STATE_RPAREN;
else if( mid_e[i] == 0x20 || mid_e[i] == '\t' )
s = STATE_BLANK;
else
s = STATE_UNKNOWN;

switch( s )
{
case STATE_DIGIT:
while( mid_e[i] != '\0' && !isdigit(mid_e[i]) )
pos_e[j++] = mid_e[i++];
break;
case STATE_OPERATOR:
if( prio(mid_e[i]) > prio(op_stack[top]) || mid_e[i] == '(' )
op_stack[++top] = mid_e[i++];
else
{
while( mid_e[i] != '\0' && prio(mid_e[i]) <= prio(op_stack[top]) )
pos_e[j++] = op_stack[top--];
op_stack[++top] = mid_e[i++];
}
break;
case STATE_RPAREN:
while( top >= 0 && op_stack[top] != '(' )
pos_e[j++] = op_stack[top--];
if( op_stack[top] != '(' )
{
printf("Miss \'(\'\n");
return 1;
}
top--;
i++;
break;
case STATE_BLANK:
i++;
break;
default:
printf("Unrecognized symbolic \'%c\'\n", mid_e[i]);
return 1;
}
}
while( top != -1 )
{
if( op_stack[top] == '(' )
{
printf("Miss \')\'\n");
return 1;
}
pos_e[j++] = op_stack[top--];
}
pos_e[j] = '\0';
return 0;
}

float calc_expr( char pos_e[] )
{
int i = 0, j;
float opr1, opr2;
float opr_stack[80];
int top = -1;

char buf[10];

state_e s = STATE_UNKNOWN;

while( pos_e[i] != '\0' )
{
if( !isdigit(pos_e[i]) )
s = STATE_DIGIT;
else if( !isop(pos_e[i]) )
s = STATE_OPERATOR;
else if( pos_e[i] == '|' )
s = STATE_DELIMITER;
else
s = STATE_UNKNOWN;
switch( s )
{
case STATE_DIGIT:
j = 0;
while( pos_e[i] != '\0' && !isdigit(pos_e[i]) )
buf[j++] = pos_e[i++];
buf[j] = '\0';
opr_stack[++top] = atof(buf);
break;
case STATE_OPERATOR:
opr2 = opr_stack[top--];
opr1 = opr_stack[top];
opr_stack[top] = calc(opr1, opr2, pos_e[i++]);
break;
case STATE_DELIMITER:
i++;
break;
default:
printf("DFA state is unknown!\n");
return -1;
}
}
return opr_stack[top];
}

ATTR_SYNTAX_TREE_NODE *create_syntax_tree( char pos_e[] )
{
int i = 0, j;
int top = -1;

ATTR_SYNTAX_TREE_NODE *p_stack[80];
ATTR_SYNTAX_TREE_NODE *p;

char buf[80];

state_e s = STATE_UNKNOWN;

memset( p_stack, 0, sizeof(ATTR_SYNTAX_TREE_NODE *) * 80);

while( pos_e[i] != '\0' )
{
if( !isdigit(pos_e[i]) )
s = STATE_DIGIT;
else if( !isop(pos_e[i]) )
s = STATE_OPERATOR;
else if( pos_e[i] == '|' )
s = STATE_DELIMITER;
else
s = STATE_UNKNOWN;
switch( s )
{
case STATE_DIGIT:
j = 0;
while( pos_e[i] != '\0' && !isdigit( pos_e[i] ) )
buf[j++] = pos_e[i++];
buf[j] = '\0';
p = (ATTR_SYNTAX_TREE_NODE *)malloc(sizeof(ATTR_SYNTAX_TREE_NODE));
assert(p);
p->t = NTYPE_VALUE;
p->lchild = NULL;
p->rchild = NULL;
p->u.value = (float)atof(buf);
p_stack[++top] = p;
break;
case STATE_OPERATOR:
p = (ATTR_SYNTAX_TREE_NODE *)malloc(sizeof(ATTR_SYNTAX_TREE_NODE));
assert(p);
p->t = NTYPE_OP;
p->u.op = pos_e[i++];
// merge sub-tree
p->rchild = p_stack[top--];
p->lchild = p_stack[top];
p_stack[top] = p;
break;
case STATE_DELIMITER:
i++;
break;
default:
printf("DFA state is unknown!\n");
return NULL;
}
}
return p_stack[top];
}

float calc_expr2( ATTR_SYNTAX_TREE_NODE *p_root )
{
float lvalue, rvalue;

if( p_root->lchild->t == NTYPE_OP )
lvalue = calc_expr2( p_root->lchild );
else
lvalue = p_root->lchild->u.value;

if( p_root->rchild->t == NTYPE_OP )
rvalue = calc_expr2( p_root->rchild );
else
rvalue = p_root->rchild->u.value;

return calc(lvalue, rvalue, p_root->u.op);

}

void delete_syntax_tree( ATTR_SYNTAX_TREE_NODE *p_root )
{
if( p_root != NULL )
{
delete_syntax_tree( p_root->lchild );
delete_syntax_tree( p_root->rchild );
free( p_root );
}
}


main.c文件

#include <stdio.h>
#include <conio.h>

#include "expr.h"

int main()
{
char mid_e[80], pos_e[80];
float result;

ATTR_SYNTAX_TREE_NODE *p_root;

gets(mid_e);
if( !mid2pos(mid_e,pos_e) )
{
p_root = create_syntax_tree(pos_e);
result = calc_expr2(p_root);
printf("= %.1f\n", result);
delete_syntax_tree( p_root );
}
getch();
return 0;
}

搜索更多相关主题的帖子: Syntax DFA tree 求值 有限状态机 
2007-09-16 08:51
yuki
Rank: 2
等 级:新手上路
威 望:5
帖 子:508
专家分:0
注 册:2005-2-4
收藏
得分:0 

以上程序只支持整数处理,无法处理输入的小数点(会被程序认为无法识别的符号'.')

使用方法,直接输入表达式,回车即可求值,例:
(12*(2+2)/3+3)-4*(2-1)+1


我们都在命运湖上荡舟划桨,波浪起伏使我们无法逃离孤行;如果我们迷失方向,波浪将指引我们穿过另一天曙光
2007-09-16 08:56
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
代码太长了,楼主有时间看一下我那个用模板函数实现的四则表达式计算吧



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言,点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge):[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-16 9:13:52编辑过]

2007-09-16 09:13
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 

yuki已经是
[QUOTE]第五级:技术工人,技术精湛[/QUOTE]
http://bbs.bc-cn.net/viewthread.php?tid=169381


九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2007-09-16 10:38
百年不亮
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:789
专家分:0
注 册:2006-4-14
收藏
得分:0 
第五级:技术工人,技术精湛,熟悉行业知识但领导能力欠加,此类人大多为系分人员或资深程序员,基本上桀骜不逊,自视清高,不愿于一般技术人员为伍,在论坛上基本以高手面目出现。


怎么看着有点像knoker,你知你是那一级。
2007-09-16 10:44
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
回复:(百年不亮)[quote]第五级:技术工人,技术精湛...
第十级:驴或傻X,会写SELECT语句就说自己精通ORALCE,连寄存器有几种都不知道就说自己懂汇编,建议全部送到倭国当IT产业工人,挣了倭国人的钱还严重打击倭国的软件业!

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2007-09-16 10:51
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 

本人也已经打入倭国内部,为大中华之梦添上一小杯泥土。


九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2007-09-16 10:54
百年不亮
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:789
专家分:0
注 册:2006-4-14
收藏
得分:0 
日本软件业杀手,中国民族英雄----Knocker

2007-09-16 10:54
yuki
Rank: 2
等 级:新手上路
威 望:5
帖 子:508
专家分:0
注 册:2005-2-4
收藏
得分:0 

我哪是技术精湛,有时写个东西要返工好几次,代码觉得自己都不堪入目。

对了,我毕业设计决定做一个编译器,大家能给点意见么?谢谢啦!


我们都在命运湖上荡舟划桨,波浪起伏使我们无法逃离孤行;如果我们迷失方向,波浪将指引我们穿过另一天曙光
2007-09-16 11:09
百年不亮
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:789
专家分:0
注 册:2006-4-14
收藏
得分:0 
听说机械工业出版社引进的O'REILLY的《lex与yacc》对理解编译原理有帮助,机械华章还有本书好像是叫《编译器构造C描述》。我明年学编译原理,现在还不了解。
2007-09-16 11:16
快速回复:[分享]使用确定式有限状态机(DFA)及语法树(Syntax tree)实现简单的 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018858 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved