Please help write a code in C that asks to translate from an infix expression (e
ID: 3723322 • Letter: P
Question
Please help write a code in C that asks to translate from an infix expression (e.g. a * (b + c ) ) to a prefix notation (i.e., *a+bc) . You may assume that all the variables are one char and that the operators are limited to +, - , *.
The infix expression is entered by the user from the command prompt. It has a maximum length of 20 characters and it must be correct – you do not need to check for correctness
Build a binary tree for the infix expression. Your application should handle parenthesis.
Develop a function to traverse the tree and print the equivalent prefix expression to the screen
Explanation / Answer
Answer :
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
typedef struct tree
{
char data; // creating structure of tree
struct tree *left;
struct tree *right;
}*pos;
pos stack[30]; // we will use stack to for the conversion purpose
int top=-1;
pos newnode(char b)
{
pos temp;
temp=(struct tree*)malloc(sizeof(struct tree)); // to create a new node in a tree we have newnode function
temp->data=b;
temp->left=NULL;
temp->right=NULL;
return(temp);
}
void push(pos temp)
{
stack[++top]=temp; // push and pop are the function of stack
}
pos pop()
{
pos p;
p=stack[top--];
return(p);
}
void inorder(pos t)
{
if(t!=NULL)
{
inorder(t->left); // inorder and preorder are the recursive functions basically used to convert infix to prefix
printf("%s",t->data);
inorder(t->right);
}
}
void preorder(pos t)
{
if(t!=NULL)
{
printf("%s",t->data);
preorder(t->left);
inorder(t->right);
}
}
void main()
{
char a[20];pos temp,t;int j,i;
clrscr();
printf(" Enter the infix expression ");
gets(a);
printf("hello");
for(i=0;a[i]!=NULL;i++)
{
if(a[i]=='*' || a[i]=='/' || a[i]=='+' || a[i]=='-')
{ /* when operator will encounter we will simply create a new node
and its two children. the parent node of these two children will be the particular operator*/
temp=newnode(a[i]);
temp->right=pop();
temp->left=pop();
push(temp);
}
else
{
temp=newnode(a[i]);
push(temp);
}
}
preorder(temp); // calling preorder method to convert inorder to preorder
printf(" ");
getch();
}