OJ Board

Code: Select all

#include <iostream.h>
#include <stdio.h>

#define MAX    100
#define E 	 	 1
#define T 		 2
#define F 		 3
#define ADD      1
#define SUB      2
#define MUL      3
#define DIV		 4

struct Node
{
	int type;
	Node *left,*right;
};
char str[MAX+1],op[]={0,43,45,42,47};

Node *createNode(int v)
{
	Node *p;
	p 	   	= new Node;
	p->type = v;
	p->left = p->right = NULL;
	return p;
}

int getPlusMinus(int start,int end,int *pos)
{
	int i,count=0;
	for(i=end;i>start;i--)
	{
		if(str[i]==')') count++;
		else if(str[i]=='(') count--;
		else if((str[i]=='+' || str[i]=='-') && !count)
			break;
	}
	if(i > start)
	{
		*pos = i;
		if(str[i]=='+')
			return ADD;
		else
			return SUB;
	}
	else
		return 0;
}

int getMulDiv(int start,int end,int *pos)
{
	int i,count=0;
	for(i=end;i>start;i--)
	{
		if(str[i]==')') count++;
		else if(str[i]=='(') count--;
		else if((str[i]=='*' || str[i]=='/') && !count)
			break;
	}
	if(i > start)
	{
		*pos = i;
		if(str[i]=='*')
			return MUL;
		else
			return DIV;
	}
	else
		return 0;
}

Node* parse(int start,int end,int type)
{
	int pos,flag;
	Node *p;

	if(type==E)
	{
		flag = getPlusMinus(start,end,&pos);
		if(!flag)
			return parse(start,end,T);
		else
		{
			p 		= createNode(flag);
			p->left = parse(start,pos-1,E);
			p->right= parse(pos+1,end,T);
			return p;
		}
	}
	else if(type==T)
	{
		flag = getMulDiv(start,end,&pos);
		if(!flag)
			return parse(start,end,F);
		else
		{
			p		= createNode(flag);
			p->left = parse(start,pos-1,T);
			p->right= parse(pos+1,end,F);
			return p;
		}
	}
	else
	{
		if(str[start]=='(')
			return parse(start+1,end-1,E);
		else
			return createNode(str[start]-'0');
	}
}

void postOrder(Node *p)
{
	if(p->left && p->right)
	{
		postOrder(p->left);
		postOrder(p->right);
		cout<<op[p->type];
		delete p;
	}
	else
	{
		cout<<p->type;
		delete p;
	}
}

int main(void)
{
	char s[80];
	int len,testCase,dataSet;
	Node *root;

	scanf("%d",&dataSet);
	getchar();
	getchar();
	for(testCase=1;testCase<=dataSet;testCase++)
	{
		for(len=0;;len++)
		{
			str[len]=getchar();
			if(str[len]=='\n' || str[len]==EOF) break;
			getchar();
		}
		str[len] = 0;
		if(len > 0)
		{
			root	 = parse(0,len-1,E);
			postOrder(root);
		}
		cout<<endl;
		if(testCase<dataSet)
			cout<<endl;
	}
	return 0;
}
[cpp][/cpp]

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct _node { char value; struct _node *left,*right; } NODE;

char *s;

NODE *E(void);

NODE *D(void)
{
	NODE *t = (NODE *)calloc(1,sizeof(NODE));

	if(*s == 0) return NULL;
	t->value = *s;
	t->left = t->right = NULL;
	s++;
	return t;
}

NODE *F(void)
{
	NODE *t;
	char ch;

	if(*s == '(')
	{
		s++;
		t = E();
		if(*s == ')') s++;
	}
	else
		t = D();
	return t;
}

NODE *T1(NODE *x)
{
	NODE *t = NULL,*p;

	if((*s == '/') || (*s == '*'))
	{
		t = (NODE *)calloc(1,sizeof(NODE));
		t->value = *s;
		s++;
		t->left = NULL;
		p = F();
		t->left = x;
		t->right = p;
		p = T1(t);
		if(p != NULL) t = p;
	}
	return t;
}

NODE *T(void)
{
	NODE *t,*p;

	p = F();
	t = T1(p);
	if(t == NULL) t = p;
	return t;
}

NODE *E1(NODE *x)
{
	NODE *t = NULL,*p;

	if((*s == '-') || (*s == '+'))
	{
		t = (NODE *)calloc(1,sizeof(NODE));
		t->value = *s;
		s++;
		t->left = NULL;
		p = T();
		t->left = x;
		t->right = p;
		p = E1(t);
		if(p != NULL) t = p;
	}
	return t;
}

NODE *E(void)
{
	NODE *t,*p;

	p = T();
	t = E1(p);
	if(t == NULL) t = p;
	return t;
}

int ReadExpression(char *s)
{
	char line[200],*t,f = 1;

	while(gets(line) != NULL)
	{
		if(line[0] == 0) break;
		f = 0;
		t = line;
		while(isspace(*t)) t++;
		*s = *t;
		s++;
	}
	if(f) return 0;
	*s = 0;
	return 1;
}

void Print(NODE *r)
{
	if(r == NULL) return;
	Print(r->left);
	Print(r->right);
	printf("%c",r->value);
	free(r);
}

int main(void)
{
	int n,N;
	char line[200];
	NODE *tree;

	scanf("%d",&N);
	gets(line);
	gets(line);
	for(n=0;n<N;n++)
	{
		if(ReadExpression(line) == 0) break;
		s = line;
		while(*s)
		{
			tree = E();
			Print(tree);
		}
		printf("\n");
		if(n < N-1) printf("\n");
	}
	return 0;
}