这里仅提供代码供大家参考学习,并希望的到大家的意见与建议。
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;
}