主题:个人写的表达式转二叉树
orangelegend
[专家分:860] 发布于 2006-12-18 00:35:00
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *CRTree(char s[],int i,int j){
int k,posi,plus=0;
BTNode *p;
if(i==j){
p=(BTNode *)malloc(sizeof(BTNode));
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
return p;
}
for(k=i;k<=j;k++){
if(s[k]=='+'||s[k]=='-'){
plus++;
posi=k;
}
}
if(plus==0)
for(k=i;k<=j;k++)
if(s[k]=='*'||s[k]=='/'){
plus++;
posi=k;
}
if(plus!=0){
p=(BTNode *)malloc(sizeof(BTNode));
p->data=s[posi];
p->lchild=CRTree(s,i,posi-1);
p->rchild=CRTree(s,posi+1,j);
return p;
}
}
void Disp(BTNode *T){
if(T!=NULL){
printf("%c",T->data);
if(T->lchild||T->rchild){
printf("(");
Disp(T->lchild);
if(T->rchild) printf(",");
Disp(T->rchild);
if(T->lchild) printf(")");
}
}
}
void main(){
char s[20];
BTNode *T;
gets(s);
T=CRTree(s,0,strlen(s)-1);
Disp(T);
}[em1][em2]
回复列表 (共15个回复)
11 楼
hqin6 [专家分:140] 发布于 2006-12-18 22:17:00
(接上面)
while (!sign_stack.IsEmpty())
{
BinaryTreeNode<T>* l,*r,*m,*mid;
num_stack.Delete(r);
num_stack.Delete(l);
sign_stack.Delete(m);
MakeTree(l,m,r);
num_stack.Add(m);
}
if (!num_stack.IsEmpty())
{
num_stack.Delete(root);
}
}
12 楼
hqin6 [专家分:140] 发布于 2006-12-18 22:18:00
(接上面)
template<class T>
void BinaryTree<T>::Show_BinaryTree()
{
vector<bool> bIsEnd;
bIsEnd.push_back(0);
cout<<"您所输入的树是:\n";
cout<<"Root:";
if (!root->LeftChild&&!root->RightChild)
{
cout<<root->data<<endl;
}
else
{
cout<<root->sign<<endl;
Print_BNode(root->LeftChild,1,bIsEnd,false);
bIsEnd[0]=1;
Print_BNode(root->RightChild,1,bIsEnd,true);
cout<<endl;
}
}
template<class T>
void BinaryTree<T>::Print_BNode(BinaryTreeNode<T> *p, int c, vector<bool>& isend,bool RorL)
{
if (!p)
{
return;
}
for(int j=0;j<c;j++)
{//─└├│
if(isend[j]==0)
if(j!=c-1)cout<<"│";
else cout<<"├";
else if(j!=c-1)cout<<" ";
else cout<<"└";
if(j!=c-1)cout<<" ";
else cout<<"─";
}
if (!p->LeftChild&&!p->RightChild)
{
cout<<" "<<p->data;
}
else
cout<<" "<<p->sign;
if (RorL)
{
cout<<"R";
}
else cout<<"L";
cout<<endl;
for(int i=0;i<2;i++)
{
if(isend.size()==c)isend.push_back(0);
else isend[c]=0;
if(i==1)
{
if(isend.size()==c)isend.push_back(1);
else isend[c]=1;
}
if (i==0)
{
Print_BNode(p->LeftChild,c+1,isend,false);
}
else Print_BNode(p->RightChild,c+1,isend,true);
}
}
template<class T>
void BinaryTree<T>::TreeCount()
{
T result=Count(root);
cout<<"运算结果为:\n"<<result<<endl;
}
template<class T>
T BinaryTree<T>::Count(BinaryTreeNode<T>*p)
{
if (!p->LeftChild&&!p->RightChild)
{
return p->data;
}
T result,l=Count(p->LeftChild),r=Count(p->RightChild);
if (p->sign=='+')
{
return l+r;
}
else if (p->sign=='-')
{
return l-r;
}
else if (p->sign=='*')
{
return l*r;
}
else if (p->sign=='/')
{
if(r==0) throw BadInput();
return l/r;
}
else if (p->sign=='%')
{
return l%r;
}
else
{
cout<<"不支持"<<p->sign<<"运算"<<endl;
exit(1);
}
}
13 楼
hqin6 [专家分:140] 发布于 2006-12-18 22:20:00
template<class T>
void BinaryTree<T>::ShowFloor()
{
LinkedQueue<BinaryTreeNode<T>*>myqueue;
int floor=1;
cout<<"遍历这棵二叉树:\n";
ShowNode(root,myqueue);
cout<<endl;
}
template <class T>
void BinaryTree<T>::ShowNode(BinaryTreeNode<T>*p,LinkedQueue<BinaryTreeNode<T>*>&myqueue)
{
if(p)
{
if (!p->LeftChild&&!p->RightChild)
{
cout<<" "<<p->data;
}
else
cout<<" "<<p->sign;
myqueue.Add(p->LeftChild).Add(p->RightChild);
}
if (myqueue.IsEmpty())
{
return;
}
BinaryTreeNode<T>*mid;
myqueue.Delete(mid);
ShowNode(mid,myqueue);
}
14 楼
hqin6 [专家分:140] 发布于 2006-12-18 22:21:00
main.cpp
××××××××
#include "tree.h"
void Pause()
{
cout<<endl<<endl<<endl;
system("pause");
cout<<endl<<endl<<endl;
}
void main()
{
try
{
BinaryTree<int>mytree;
mytree.InputBinaryTree();
Pause();
mytree.Show_BinaryTree();
Pause();
mytree.TreeCount();
Pause();
mytree.ShowFloor();
Pause();
mytree.DeleteTree();
Pause();
}
catch (OutOfBounds)
{
cout<<"越界!"<<endl;
}
catch (BadInput)
{
cout<<"输入有误!"<<endl;
}
}
15 楼
414994007 [专家分:0] 发布于 2006-12-21 18:02:00
小弟自愧不如,请帮忙编个程序:
1、 运算器
问题描述:加减乘运算器。
要 求:使用给定文件进行输入输出,必须采用双向链表实现任意位数的正负整数或小数的加法、减法和乘法运算。每个结点存储一位数字。算出的结果若是小数,整数部分的高位若为0要去掉,小数部分的低位若为0要去掉,若0085.56700,最后结果应为85.567。
文件说明:给定的文件a*.txt为第一个数,b*.txt为第二个数,要求加法产生的结果存储在add*.txt中,减法产生的结果存储在sub*.txt中,乘法产生的结果存储在mul*.txt中,*为对应的一组数据,共给出十组数据。并提供十组加减乘结果,供大家对照参考。
我来回复