主题：表达式类型的实现 二叉树
wlp108696
[专家分：0] 发布于 2011-12-07 20:26:00
求助，求助！各位大侠，小妹现有一个编程问题不懂如何编写，我是一个初级者，望各位帮帮忙啦！
问题：写一个程序，实现基于二叉树的算术表达式Expression的操作。假设Expession内含有变量（a-z），常量（0-9），二元运算符（+，-，*，/，^）,实现以下操作：
（1）ReadExpr（E）——以字符序列的形式输入语法正确的前缀表达式并构造表达式E
（2）WriteExpr（E）——用带括弧的中缀表达式输出表达式E
（3）Assign（V,c）——实现对变量V的赋值（V=c），变量的初值为0
（4）Value（E）——对算术表达式E求值
（5）CompoundExpre（P,E1，E2）——构造一个新的复合表达式（E1）P（E2）
希望给我一个有注释的编程啊，小妹在这先谢过啦！
回复列表 （共2个回复）
沙发
suosuopuo [专家分：40] 发布于 2011-12-08 15:55:00
我试着写了一个。。。
[code=c]
#include <stdio.h>
#include <stdlib.h>
#define IS_OP(c) (c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
#define IS_VA(c) ('a'<=c && c<='z')
#define IS_CO(c) ('0'<=c && c<='9')
#define IS_SPACE(c) (c==' '||c=='\t')
enum node_type{OP=1,VA,CO=4};
typedef struct _node{
int value;
enum node_type type;
struct _node *left,*right;
}node_t;
int variables[26]={0};
static int read_expr(node_t **e)
{
int c,ret=0; /*ret的初始值为0*/
if((*e=malloc(sizeof(node_t)))==NULL)
{
printf("mallco error!\n");
exit(-1);
}
(*e)->left=(*e)->right=NULL;
while(c=getchar(),IS_SPACE(c))
;
switch(IS_OP(c)+(IS_VA(c)<<1)+(IS_CO(c)<<2))
{
case OP:
(*e)->type=OP;
(*e)->value=c;
if((ret=read_expr(&(*e)->left))==0)
ret=read_expr(&(*e)->right);
break;
case VA:
(*e)->type=VA;
(*e)->value=c-'a';
break;
case CO:
(*e)->type=CO;
(*e)->value=c-'0';
break;
default:
printf("expression error!\n");
return -1; /*其它已分配的空间用free_all()释放*/
}
return ret;
}
static void write_expr(node_t *e)
{
switch(e->type)
{
case OP:
putchar('(');
write_expr(e->left);
putchar(e->value);
write_expr(e->right);
putchar(')');
break;
case VA:
putchar(e->value+'a');
break;
case CO:
putchar(e->value+'0');
break;
}
}
static double value(node_t *e)
{
switch(e->type)
{
case OP:
switch(e->value)
{
case '+':
return value(e->left)+value(e->right);
case '-':
return value(e->left)-value(e->right);
case '*':
return value(e->left)*value(e->right);
case '/':
return value(e->left)/value(e->right);
case '^':
{
double rvalue=value(e->right);
double lvalue=value(e->left);
double res;
for(res=1;rvalue>0;rvalue--)
res*=lvalue;
return res;
}
}
case VA:
return variables[e->value];
case CO:
return e->value;
}
}
[/code]
板凳
suosuopuo [专家分：40] 发布于 2011-12-08 15:56:00
后半，给分么。。。
[code=c]
static node_t* compound_expr(int p,node_t *e1,node_t *e2)
{
node_t *root;
if((root=malloc(sizeof(node_t)))==NULL)
{
printf("malloc error\n");
exit(-1);
}
root->type=OP;
root->value=p;
root->left=e1;
root->right=e2;
return root;
}
/*
*释放二叉树的空间
*/
static void free_rec(node_t *e)
{
if(e->left!=NULL)
free_rec(e->left);
if(e->right!=NULL)
free_rec(e->right);
free(e);
}
/*
*read_expr()的包装函数
*/
void ReadExpr(node_t **e)
{
while(1)
{
printf("input a expression: ");
if(read_expr(e)==0)
{
getchar();
return;
}
free_rec(*e);
getchar();
}
}
/*
*write_expr()的包装函数
*/
void WriteExpr(node_t *e)
{
printf("the expression is: ");
write_expr(e);
putchar('\n');
}
/*
*assign操作较简单，没有用包装函数
*/
void Assign()
{
int vname,vvalue;
printf("assign a variable: ");
while(vname=getchar(),!IS_VA(vname))
;
while(vvalue=getchar(),!IS_CO(vvalue))
;
getchar();
variables[vname-'a']=vvalue-'0';
}
/*
*value()函数的包装函数
*/
void Value(node_t *e)
{
printf("expression's value: %f\n",value(e));
}
/*
*compound_expr()的包装函数
*/
node_t* CompoundExpr(node_t *e1,node_t *e2)
{
int op;
printf("intput a new operator: ");
while(op=getchar(),!IS_OP(op))
;
getchar();
return compound_expr(op,e1,e2);
}
int main()
{
node_t *root1;
node_t *root2;
node_t *root3;
ReadExpr(&root1);
WriteExpr(root1);
Value(root1);
Assign();
ReadExpr(&root2);
WriteExpr(root2);
Value(root2);
root3=CompoundExpr(root1,root2);
WriteExpr(root3);
Value(root3);
}
[/code]
我来回复
您所在位置：