4 Replies - 22752 Views - Last Post: 10 September 2008 - 07:43 PM Rate Topic: -----

#1 roussey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 08-July 08

infix expression to binary tree

Posted 14 July 2008 - 04:58 AM

Hi,

I need some help.
I need to take an infix expression as input and convert it to a binary tree and them evaluate and give the answer of the expression. But I don't know how to do this conversion using C. Can someone help me?

Thanks,
Is This A Good Question/Topic? 0
  • +

Replies To: infix expression to binary tree

#2 gabehabe  Icon User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1382
  • View blog
  • Posts: 10,962
  • Joined: 06-February 08

Re: infix expression to binary tree

Posted 14 July 2008 - 05:31 AM

[rules][/rules]
Was This Post Helpful? 0
  • +
  • -

#3 born2c0de  Icon User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 180
  • View blog
  • Posts: 4,667
  • Joined: 26-November 04

Re: infix expression to binary tree

Posted 14 July 2008 - 07:47 AM

Your answer lies in this tutorial.
Was This Post Helpful? 0
  • +
  • -

#4 roussey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 08-July 08

Re: infix expression to binary tree

Posted 14 July 2008 - 10:51 AM

View Postgabehabe, on 14 Jul, 2008 - 05:31 AM, said:

[rules][/rules]


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
//#include "arvore.h"

/*
*  tree function
*/

struct arv{
char info;
char op;
int num;
struct arv *esq;
struct arv *dir;
};

typedef struct arv *Arv;

Arv cria_vazia(void){ //create empty tree
return NULL;
}

Arv arv_libera(Arv a){ free tree
if(!arv_vazia(a)){
arv_libera(a->esq);
arv_libera(a->dir);
free(a);
}
return NULL;
}

int arv_vazia(Arv a){ verify if tree is empty
return a==NULL;
}

/*
* stack functions
*/

struct stack_s {
Arv *area;
int size;
int index;
};

typedef struct stack_s *stack;

stack stack_create(int s) { //create stack
stack p = malloc(sizeof(struct stack_s));
if( p == NULL ) {
//error(ERROR_NOMEM);
exit(-1);
};
p->area = malloc(s*sizeof(struct arv));
if( p->area == NULL ) {
//error(ERROR_NOMEM);
exit(-1);
};
p->size = s;
p->index = 0;
return p;
}

void stack_destroy(stack p) { free stack space
free(p->area);
free(p);
}

int stack_push(stack p, Arv x) {
if( p->index >= 30 )
return -1;
p->area[p->index ++] = x;
return 0;
}

int stack_pop(stack p, Arv *px) {
if( p->index <= 0 )
return -1;
*px = p->area[--(p->index) ];
return 0;
}

Arv stack_top(stack p) {//top of stack
if( p->index > 0 )
return p->area[p->index-1];
return 0;
}

int stack_empty(stack p) { //verify if the stack is empty
if( p->index<= 0 )
return 1;
else
return 0;
}

/*
* procedimento: getline
* finalidade : ler uma linha de maneira segura usando biblioteca C padrao
* parametros
* - entrada:
* s = apontador para area de armazenamento da linha
* nmax = tamanho maximo da linha incluindo o zero final
* - saida:
* s = linha lida sem o \n final se houver
* - retorna
* > 0 = tamanho da linha
* -1 = final de arquivo
* -2 = erro
* -3 = linha cortada (era maior que nmax)
*/
int getline(char *s, int nmax){
int ns;

if(feof(stdin)){
return -1;
}
if(fgets(s,nmax,stdin)==NULL){
return -2;
}
ns = strlen(s);
if(ns > 1 && s[ns - 1] == '\n'){
s[ns - 1] = 0;
return 0;
}
return -3;
}

void infix2exptree(char *infix, int nmax, Arv *r){ //infix to expression tree
stack operando;
stack operador;
char numero;
char *p;
int ns, i;
Arv newnode, oper , op_esq, op_dir;

operando = stack_create(30);
operador = stack_create(30);
ns = strlen(s);
p = &infix[0];
strcpy(numero,"");
while(*p){

while(*p == ' ' || *p == '\t'){//pula espaços
p++;
}

if(isdigit(*p)){
while(isdigit(*p)){
strcat(numero,p);
p++;
}
newnode = (Arv)malloc(sizeof(struct arv));
newnode->info = 'N';
newnode->num = atoi(numero);
newnode->esq = NULL;
newnode->dir = NULL;
stack_push(operador,newnode);
}
else if(*p == '('){
newnode = (Arv)malloc(sizeof(struct arv));
newnode->info = 'O';
newnode->op = '(';
newnode->esq = NULL;
newnode->dir = NULL;
stack_push(operando,newnode);
}
else if(*p == ')'){
while(stack_top(operador)->op != '('){
stack_pop(operador,&oper);
stack_pop(operando,&op_dir);
stack_pop(operando,&op_esq);
newnode = (Arv)malloc(sizeof(struct arv));
newnode->info = 'O';
new_node->op = oper;
newnode->esq = op_esq;
newnode->dir = op_dir;
stack_push(operando,newnode);
stack_pop(operador,&oper);
}
}
else{ //sobraram os operadores
newnode = (Arv)malloc(sizeof(struct arv));
newnode->info = 'O';
new_node->op = *p;
newnode->esq = NULL;
newnode->dir = NULL;

if(precedencia(*p) <= precedencia(stack_top(operador)->op)){// arg1 menor ou igual em precedencia que arg2
stack_pop(operador,&oper);
stack_pop(operando,&op_dir);
newnode->dir = op_dir;
stack_pop(operando,&op_esq);
newnode->esq = op_esq;
stack_push(operando,newnode);
}
else{
stack_push(operador,newnode);
}
}
p++;
}
while(!stack_empty(operador)){
stack_pop(operador,&oper);
stack_pop(operando,&op_dir);
stack_pop(operando,&op_esq);
newnode = (Arv)malloc(sizeof(struct arv));
newnode->info = 'O';
new_node->op = oper;
newnode->esq = op_esq;
newnode->dir = op_dir;
stack_push(operando,newnode);
}
stack_destroy(operador);
stack_pop(operando,&r);
stack_destroy(operando);
}

int precedencia(char e){
int pri = 0;

if(e == '*' || e == '/'){
pri = 2;
}
else if(e == '+' || e == '-'){
pri = 1;
}
return pri;
}


int main (void){
char linha[100];
int linhamax = 100;
int rc;
Arv *r


while(1){

printf(">>");
rc = getline(linha,linhamax);
if(rc < 0){
break;
}
printf(">>%s\n",linha);
infix2exptree(linha,linhamax,&r);


}
return 0;
}



the problem is that it seems that there is no errors anymore, but it doesn't create the tree. I think there is some pointer ni wrong way, don't know.
Was This Post Helpful? 0
  • +
  • -

#6 Pawankumarjha  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 2
  • Joined: 10-September 08

Re: infix expression to binary tree

Posted 10 September 2008 - 07:43 PM

Make a Binary tree from Infix expression.

Infix :-> 4 $ 2 * 3 - 3 + 8 / 4 / (1 + 1)

Solution: First separate the operator and operand
___________________________________________________________

Operator:-> $ * - + / / (+)

Operand:-> 4 2 3 3 8 4 1 1
___________________________________________________________

Now separate the operator according to their priority

First priority :-> ( + ) // Because ( ) has greater priority

Second priority :-> $

Third priority :-> * / /

Fourth priority :-> - +
_____________________________________________________
Step 1:
_____________________________________________________

Root will be fixed according to lowest priority

So, In Foruth priority - +

Here + will be the first root of tree (right to left)

+
_________________________________________________
Step 2:
_________________________________________________


Now - will be the left child of root of this tree

Because - is existing in left side of +.

+
/
/
-

_________________________________________________
Step 3:
_________________________________________________

Now in Third priority :-> * / /

Here / will be right child of +.

Because / is existing in right side of +.
+
/ \
/ \
- /

_________________________________________________
Step 4:
_________________________________________________

Here / will be right child of /.

Because / is existing in left side of /.
+
/ \
/ \
- (/) Devide sign (no 1)
/
/
(/) devide sign (no 2)

_________________________________________________
Step 5:
_________________________________________________
Here * will be left child of -.

Because, In infix expression, * is existing in left side of -.

+
/ \
/ \
- (/) Devide sign (no 1)
/ /
/ /
* (/) devide sign (no 2)

_________________________________________________
Step 6:
_________________________________________________

In Second priority:-> $

Here $ will be left child of *.

Because, In infix expression,

$ is existing in left side of *.

+
/ \
/ \
- (/) Devide sign (no 1)
/ /
/ /
* (/) devide sign (no 2)
/
/
$
_________________________________________________
Step 7:
_________________________________________________

In First priority:-> (+)

Here (+) will be left child of / (devide sign no 1).

Because, In infix expression,

$ is existing in left side of *.

+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/
/
$

_________________________________________________
Step 8:
_________________________________________________

Now As we know the expression is

Infix :-> 4 $ 2 * 3 - 3 + 8 / 4 / (1 + 1)

Operand:-> 4 2 3 3 8 4 1 1

Now put the operand only

_____________________________________________________

First of all take 4, Here 4 will be left child of $.

Because 4 is left side of $ in expression

+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/
/
$
/
/
4
_____________________________________________________

Now take 2 , Here 2 will be right child of $.

Because 2 is right side of $ in expression.

+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/
/
$
/ \
/ \
4 2
_____________________________________________________

Now take 3 , Here 3 will be right child of *.

Because 3 is right side of * in expression.

+
/ \
/ \
- (/)
/ / \
/ / \
* (/) +
/ \
/ \
$ 3
/ \
/ \
4 2

_____________________________________________________

Now take 8, Here 8 will be left child of /(devide sign no 2).

Because 8 is left side of / in expression. Here i am not saying that 8 will be right child of +. Because / is the right child of +. And operand won't be root in Tree. So i am taking Here 8 will be left child of /(devide sign no 2).

+
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) +
/ \ /
/ \ /
$ 3 8
/ \
/ \
4 2

________________________________________________________

Now take 4, Here 4 will be right child of /(devide sign no 2).

Because 4 is right side of / in the given expression.

+(first +)
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) + (second +)
/ \ / \
/ \ / \
$ 3 8 4
/ \
/ \
4 2

________________________________________________________

Now take 1, Here 1 will be left child of + (second +).

Because 1 is right side of /(devide sign no 2) in the given expression.

+ (first +)
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) + (second +)
/ \ / \ /
/ \ / \ /
$ 3 8 4 1
/ \
/ \
4 2


________________________________________________________

Now take 1, Here 1 will be right child of + (second +).

Because 1 is right side of + (second +) in the given expression.

+
/ \
/ \
- (/)
/ \ / \
/ \ / \
* 3 (/) +
/ \ / \ / \
/ \ / \ / \
$ 3 8 4 1 1
/ \
/ \
4 2

-------------------------------------------
The final Tree for an expression |
|
Infix :-> 4 $ 2 * 3 - 3 + 8 / 4 / (1 + 1) |
|
-------------------------------------------
|
+ |
/ \ |
/ \ |
- (/) |
/ \ / \ |
/ \ / \ |
* 3 (/) + |
/ \ / \ / \ |
/ \ / \ / \ |
$ 3 8 4 1 1 |
/ \ |
/ \ |
4 2 |
|
-------------------------------------------


If you don't understand my point. So mail me at pankajace12@gmail.com

Know my profile

http://www.scodz.com...le.php?uid=1451

Attached File(s)


Was This Post Helpful? 1

Page 1 of 1