Cod sursa(job #361456)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 5 noiembrie 2009 10:32:54
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
/*
   Construirea unui arbore de expresie

   Ideea de baza a algoritmului este cea urmarita si in JOB ID 185143

   Parcurgem expresia tinand cont de nivelurile subexpresiilor
   si de nivelurile de prioritate a operatorilor
*/
#include <cstdio>
#include <cstring>
#define NX 100
#define LMAX 2
char op[4][4] = { "+-", "*/", "^", "" };
char S[NX], *p;

struct node {
	char val,op;
	node *l, *r;
	node( char a = 0, char b = 0, node *c = 0, node *d = 0 ) :
		val(a), op(b), l(c), r(d) {}
} *A;

node *expr( int lev ) {

	node *x, *y;
	if( lev == LMAX+1)
		if( *p == '(' )
			++p, x = expr(0), ++p;
		else
			for( x = new node(); (*p >= '0' && *p <= '9')||(*p>='a'&&*p<='z'); ++p )
				x->val=*p;
	else
		for( x = expr( lev+1 ); strchr( op[lev], *p ); x = y )
			y = new node( 0, *p++, x, expr( lev+1 ) );
	return x;
}

void postordine(node *p)
{
    if(p->val!=0)
      printf("%c",p->val);
    else printf("%c",p->op);
    if(p->l!=NULL) postordine(p->l);
    if(p->r!=NULL) postordine(p->r);
}


int main() {
	freopen( "evaluare.in", "r", stdin );
	freopen( "evaluare.out", "w", stdout );

	fgets( S, NX, stdin ), p = S;
	A = expr( 0 );
    postordine(A);
	return 0;
}