Please help write a code in C that asks to translate from an infix expression (e
ID: 3722822 • 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
#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();
}
please ask in comment section if you understand any part of code and if the program is not running in your IDE due to some reason then kindly comment. I'll fix the problem immediately. and please thumbs up my answer :)