Please help write a code in C that asks to translate from an infix expression (e
ID: 3724186 • 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
The code is given as follows. Support of whitespace characters is also added.
Please Note: I didn't read the tree part. So Im now giving you the solution using expression tree
Using Expression Tree
Example Output
Enter the infix expression
a * (b + c)
Preorder traversal:
*a+bc
Code
// The code is given as follows. Support of whitespace characters is also added.
// Using Expression Tree
// Example output
// Enter the infix expression
// a * (b + c )
// *a+bc
// Best Regards
// Code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define maxsize 20
typedef struct node
{ char data;
struct node *left;
struct node *right;
}
btree;
/*stack stores the operand nodes of the tree*/
btree *stack[maxsize];
int top;
struct mystack {
int stack_top;
unsigned size;
int* array;
};
char *strreverse(char *str) {
char *p1, *p2;
if (! str || ! *str)
return str;
for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2) {
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
}
return str;
}
int isEmpty(struct mystack* mystack) {
return mystack->stack_top == -1 ;
}
char stack_top(struct mystack* mystack) {
return mystack->array[mystack->stack_top];
}
struct mystack* makemystack( unsigned size ) {
struct mystack* mystack = (struct mystack*) malloc(sizeof(struct mystack));
if (!mystack)
return NULL;
mystack->stack_top = -1;
mystack->size = size;
mystack->array = (int*) malloc(mystack->size * sizeof(int));
if (!mystack->array)
return NULL;
return mystack;
}
char stack_pop(struct mystack* mystack) {
if (!isEmpty(mystack))
return mystack->array[mystack->stack_top--] ;
return '$';
}
void RemoveSpaces(char* source)
{
char* i = source;
char* j = source;
while(*j != 0)
{
*i = *j++;
if(*i != ' ')
i++;
}
*i = 0;
}
void stack_push(struct mystack* mystack, char op) {
mystack->array[++mystack->stack_top] = op;
}
int isOperand(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int Prec(char ch)
{
switch (ch) {
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
}
return -1;
}
int infixstack_topostfix(char* exp)
{
int i, k;
struct mystack* mystack = makemystack(strlen(exp));
if(!mystack) // See if mystack was maked successfully
return -1 ;
for (i = 0, k = -1; exp[i]; ++i)
{
if (isOperand(exp[i]))
exp[++k] = exp[i];
else if (exp[i] == '(')
stack_push(mystack, exp[i]);
else if (exp[i] == ')')
{
while (!isEmpty(mystack) && stack_top(mystack) != '(')
exp[++k] = stack_pop(mystack);
if (!isEmpty(mystack) && stack_top(mystack) != '(')
return -1; // invalid expression
else
stack_pop(mystack);
}
else // an operator is encountered
{
while (!isEmpty(mystack) && Prec(exp[i]) <= Prec(stack_top(mystack)))
exp[++k] = stack_pop(mystack);
stack_push(mystack, exp[i]);
}
}
// stack_pop all the operators from the mystack
while (!isEmpty(mystack))
exp[++k] = stack_pop(mystack );
exp[++k] = '';
}
btree *root;
btree *create(char exp[80]);
void preorder(btree *root);
int main(int argc, char const *argv[])
{
char infix[100];
printf("Enter the infix expression ");
fgets(infix, 100, stdin);
RemoveSpaces(infix);
infixstack_topostfix(infix);
top=-1; /*Initialize the stack*/
root=create(infix);
printf(" Preorder traversal: ");
preorder(root);
print(" ");
return 0;
}
btree *create(char exp[]) {
btree *temp;
int pos;
char ch;
void push(btree*);
btree *pop();
pos=0;
ch=exp[pos];
while(ch!='') {
/*create new node*/
temp=((btree*)malloc(sizeof(btree)));
temp->left=temp->right=NULL;
temp->data=ch;
if(isalpha(ch))
push(temp);
else if(ch=='+' ||ch=='-' || ch=='*' || ch=='/') {
temp->right=pop();
temp->left=pop();
push(temp);
}
else
printf(" Invalid char Expression ");
pos++;
ch=exp[pos];
}
temp=pop();
return(temp);
}
void push(btree *Node) {
if(top+1 >=maxsize)
printf("Error:Stack is full ");
top++;
stack[top]=Node;
}
btree* pop() {
btree *Node;
if(top==-1)
printf(" error: stack is empty.. ");
Node =stack[top];
top--;
return(Node);
}
/* functions for tree traversal*/
void preorder(btree *root) {
btree *temp;
temp=root;
if(temp!=NULL) {
printf("%c",temp->data);
preorder(temp->left);
preorder(temp->right);
}
}