| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1270 人关注过本帖
标题:二叉树实现中缀表达式转换为后缀表达式 小小问题 望看下
取消只看楼主 加入收藏
wwlyf52o1314
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2010-3-26
结帖率:0
收藏
 问题点数:0 回复次数:0 
二叉树实现中缀表达式转换为后缀表达式 小小问题 望看下
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <stack>
#include <string.h>


#define STACK_INIT_SIZE 100
#define DATA_SIZE 10
#define STACKINCREMENT 10
#define OK    1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
using namespace std;

typedef float SElemtype;
typedef int Status;
typedef char * TElemType;

typedef struct BiTNode {
    TElemType data;
    int len; //data字符串中字符的个数
    struct BiTNode * lchild, * rchild;
}BiTNode, *BiTree;



Status IsDigital(char ch)
 {
       if(ch>='0'&&ch<='9')
       {
              return 1; //是数字字母
       }
       return 0; //不是数字字母
 }

int CrtNode(stack <BiTree> &PTR, char *c)
{
    BiTNode * T;

    int i=0;
    T = (BiTNode *)malloc(sizeof(BiTNode));
    T->data = (char *)malloc(DATA_SIZE*sizeof(char));

    while(IsDigital(c[i]))
    {
        T->data [i] = c[i];
        i++;
    }

    T->len = i;
    T->lchild = T->rchild = NULL;
    PTR.push (T);

    return i;
}

void CrtSubTree(stack <BiTree> &PTR, char c)
{
    BiTNode * T;

    T = (BiTNode *)malloc(sizeof(BiTNode));
    T->data = (char *)malloc(DATA_SIZE*sizeof(char));

    T->data [0] = c;
    T->len = 1;
    T->rchild = PTR.top(); //先右子树,否则运算次序反了
    PTR.pop ();
    T->lchild = PTR.top();
    PTR.pop ();
    PTR.push (T);
}

char symbol[5][5]={{'>', '>', '<', '<', '>'},        //符号优先级
                     {'>', '>', '<', '<', '>'},
                     {'>', '>', '>', '>', '>'},
                     {'>', '>', '>', '>', '>'},
                    {'<', '<', '<', '<', '='}};
                  
int sym2num(char s)                             //返回符号对应优先级矩阵位置
{
      switch(s)
      {
          case '+':     return 0;     break;
          case '-':     return 1;     break;
          case '*':     return 2;     break;
          case '/':     return 3;     break;
          case '#':     return 4;      break;
      }
}
char Precede(char a, char b)                    //返回符号优先级
{
      return(symbol[sym2num(a)][sym2num(b)]);
}

void CrtExptree(BiTree &T, char exp[])
{//根据字符串exp的内容构建表达式树T


    stack <BiTree> PTR;//存放表达式树中的节点指针
    stack <char> OPTR;//存放操作符

    char op;
    int i=0;

    OPTR.push ('#');
    op = OPTR.top();

    while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //与
    {
        if (IsDigital(exp[i]))
        {//建立叶子节点并入栈 PTR
            i+=CrtNode(PTR, &exp[i]);
            
        }
        else if (exp[i] == ' ')
            i++;
        else{
            switch (exp[i])
            {
                case '(': {
                    OPTR.push (exp[i]);
                    i++;
                    break;}
                case ')': {
                    op = OPTR.top (); OPTR.pop ();
                    while(op!='('){
                        CrtSubTree(PTR, op);
                        op = OPTR.top (); OPTR.pop ();
                    }//end while
                    i++;
                    break;}
                default: //exp[i]是 + - * /
                    while(! OPTR.empty ())
                    {
                        op = OPTR.top ();
                        if (Precede(op, exp[i])=='>')
                        {
                            CrtSubTree(PTR, op);
                            OPTR.pop ();
                        }

                    if(exp[i]!='#')
                    {
                        OPTR.push (exp[i]);
                        i++;
                    }
                    break;}
            }//end switch
        }//end else

    }//end while

    T = PTR.top();

    PTR.pop ();

}



void PostOrderTraverse(BiTree &T, char * exp ,int &count)
{
//后序遍历表达式树T,获取树中每个结点的数据值生成 逆波兰表达式 exp
//T是表达式树的根节点;字符串exp保存逆波兰表达式;count保存exp中字符的个数
//后序遍历中,处理根结点时,依据T->len的值,把T->data中的字符依次添加到当前exp字符串的尾端
//添加完T->data后,再添加一个空格字符,同时更新count计数器的值。

//填空
    int i;
       if(T){
         PostOrderTraverse(T->lchild);
      //后序访问左子树        
         PostOrderTraverse(T->rchild);
      //后序访问右子树
        for(i=0;i<=T->len;i++)
        {exp(i)=T->data;
        count++;
        }
    }
    return OK;
}//PostOrderTraverse
}
//填空
evaluate (char *exp,float ans)  //逆波兰表达式计算
{int i,top=0;
float d,m,n;
while(exp[i++]!='#')
{d=exp(i++)-'0';
if(exp[i++]>='0'  && exp[i++]<='9')
{top++;
push(Stack,exp[i++]);
}
else
{switch(exp[i++])
{  case '+':push(Stack,pop(Stack,m)+pop(Stack,n));break;
   case '-':push(Stack,pop(Stack,m)-pop(Stack,n));break;
   case '*':push(Stack,pop(Stack,m)*pop(Stack,n));break;
   case '/':
       if(n!=0)
       push(Stack,pop(Stack,m)/pop(Stack,n));
       else  printf("Error\n");
       break;
}
top--;
}
}
ans=Stack[top];
printf("%f\n",Stack[top]);
   
}


main()
{

    BiTree T;
    Status St;

     char ch[100],c; //输入的四则运算表达式
    char exp[100]; //逆波兰表达式
   
    int count=0;
    int i=0;
    float result;

 
     printf("请输入表达式。回车表示结束\n");
     while(i<100)
     {
         scanf("%c",&c);
         ch[i++]=c;
         if(c=='\n'){
             ch[--i]='#';
             break;
         }//end if
     }

    CrtExptree(T, ch);//根据字符串ch的内容构建表达式树T
   
    //后序遍历表达式树T得到表达式的 逆波兰表达式 exp;count中保存exp中
    PostOrderTraverse(T, exp, count);
   
    printf("逆波兰表达式为\n");
    for(i=0; i<count; i++)
        printf("%c",exp[i]);
    printf("\n");

    exp[count] = '#'; //添加结束符

    St = evaluate (exp, result); //计算 逆波兰表达式 exp 的值
   
    //输出计算的结果
    if (St)
        printf("result is  %5.2f \n", result);
    else
         printf("\n表达式错误\n");
     return 0;

}
  注:编译是出现Cannot open include file: 'exception': No such file or directory
的情况.程序不能运行....


[ 本帖最后由 wwlyf52o1314 于 2010-4-19 22:30 编辑 ]
搜索更多相关主题的帖子: 二叉树 后缀 表达 
2010-04-19 22:28
快速回复:二叉树实现中缀表达式转换为后缀表达式 小小问题 望看下
数据加载中...
 
   



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

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