Question Details The input may contain numbers, valuables, arithmetic operations

Question

Question Details
The input may contain numbers, valuables, arithmetic operations *, /, +, and -, as well as parentheses. The expression need not be fully parenthesized, and when parentheses are missing, the usual C++ precedence rules are used to determine the order of evaluation. Your program should allow the user to enter additional expressions until the user wishes to end the program. For a more difficult assignment, enhance your program so that the expression need not be well formed; if it is not well formed, then the user is asked to reenter the expression.

The infix to postfix is done but infix to prefix is not. I could really use some more help with this, Thanks!!!


//Header file
#ifndef H_StackType
#define H_StackType
#include <iostream>
#include<cassert>
using namespace std;
template <class Type>
class stackType
{
private :
int maxStackSize;
int stackTop;
Type *list;
public :
void initializeStack();
bool isFullStack() const;
bool isEmptyStack() const;
void push( const Type& );
void pop();
Type top() const;
stackType( int = 20 );
~stackType();
};
template <class Type>
void stackType<Type>::initializeStack()
{
stackTop = 0;
}
template <class Type>
bool stackType<Type>::isFullStack() const
{
return ( stackTop == maxStackSize );
}
template <class Type>
bool stackType<Type>::isEmptyStack() const
{
return ( stackTop == 0 );
}
template <class Type>
void stackType<Type>::push( const Type& newItem )
{
if ( !isFullStack() )
{
list[ stackTop ] = newItem;
stackTop++;
}
else
cout << " Can not add to a full stack";
}
template <class Type>
void stackType<Type>::pop()
{
if ( !isEmptyStack() )
stackTop--;
else
cout << " Can not remove from an empty stack";
}
template <class Type>
Type stackType<Type>::top() const
{
assert( stackTop != 0 );
return list[ stackTop - 1 ];
}
template <class Type>
stackType<Type>::stackType( int stackSize )
{
if ( stackSize <= 0 )
{
cout << "Invalid size";
stackSize = 10;
}
else
maxStackSize = stackSize;

stackTop = 0;
list = new Type[ maxStackSize ];
}
template <class Type>
stackType<Type>::~stackType()
{
delete[] list;
}

#endif

#include<string>
#include"myStack.h"
using std::string;
bool isOperator(const char c)
{

if ( ( c == '+' ) || ( c == '-' ) || ( c == '*' ) ||
( c == '/' ) || ( c == '^' ) || ( c == '%' ) )
return true;
else
return false;
}
int precedence( const char op1, const char op2 )
{
int pre1, pre2;
if ( ( op1 == '^' ) || ( op2 == '^' ) )
cout << "Exponentiation was not considered"<< "for precedence. The program may" << "result in abnormal output of Postfix exp.";

if ( ( op1 == '+' ) || ( op1 == '-' ) )
pre1 = 0;
else
if ((op1 == '*') || (op1 == '/') || (op1 == '%'))
pre1 = 1;

if ( ( op2 == '+' ) || ( op2 == '-' ) )
pre2 = 0;
else
if ((op2 == '*') || (op2 == '/') || (op2 == '%'))
pre2 = 1;

if ( pre1 == pre2 )
return 0;
else
if ( pre1 > pre2 )
return 1;
else
return -1;
}

void infixToPostfix( string infix )
{
stackType< char > myStack;
string pfx = "";
cout << " The infix expression is : " <<infix;
infix.append( ")" );
myStack.push( '(' );
unsigned int i = 0;
do
{if ( isOperator ( infix[ i ] ) )
{
if ( isOperator( myStack.top() ) )
{
if (precedence(infix[i], myStack.top())==0)
{
pfx = pfx + myStack.top();
myStack.pop();
}
else
if (precedence(infix[i],myStack.top())==1)
{
myStack.push( infix[ i ] );
i++;
}
else
{
pfx = pfx + myStack.top();
myStack.pop();
}
}
else
{

myStack.push( infix[ i ] );
i++;
}
}
else
{
if ( infix[ i ] == ')' )
{

while ( myStack.top() != '(' )
{
pfx = pfx + myStack.top();
myStack.pop();
}
myStack.pop();
i++;
}
else
if ( infix[ i ] == '(' )
{
myStack.push( infix[ i ] );
i++;
}
else
{

pfx = pfx + infix[ i ];
i++;
}
}
} while ( i < infix.length() );

cout << " The postfix expression is : " << pfx;
}

int main()
{

cout <<" Program that converts an infix expression" << " into an equivalent postfix expression";
string inFix = "";
cout << " Enter an input expression : ";
cin >> inFix;
infixToPostfix( inFix );
cout << " ";
system("pause");
return 0;
}

Explanation / Answer

INFIX, POSTFIX AND PREFIX Consider a simple expression : A + B This notation is called Infix Notation. A + B in Postfix notation is A B + As you might have noticed, in this form the operator is placed after the operands (Hence the name 'post'). Postfix is also known as Reverse Polish Notation. Similarly for Infix, the operator is placed INside the operands. Likewise the equivalent expression in prefix would be + A B, where the operator precedes the operands. So if X1 and X2 are two operands and OP is a given operator then Quote infix postfix prefix X1 OP X2 = X1 X2 OP = OP X1 X2 We use infix notation for representing mathematical operations or for manually performing calculations, since it is easier to read and comprehend. But for computers to perform quick calculations, they must work on prefix or postfix expressions. You'll soon find out why once you understand how expressions are evaluated. Now let's take a slightly complicated expression : A + B / C How do we convert this infix expression into postfix? For this we need to use the BODMAS rule. (Remember?) This rule states that each operator has its own priority and the operators with the highest priority are evaluated first. The operator priority in Descending order is BODMAS which is: B O D M A S Bracket Open -> Division -> Multiplication -> Addition -> Subtraction [MAX. PRIORITY] [MIN. PRIORITY] Hence, in the preceding example, B / C is evaluated first and the result is added to A. To convert A + B / C into postfix, we convert one operation at a time. The operators with maximum priority are converted first followed by those which are placed lower in the order. Hence, A + B / C can be converted into postfix in just X steps. :: A + B / C (First Convert B / C -> B C /) 1: A + B C / (Next Operation is A + (BC/) -> A BC/ + 2: A B C / + (Resultant Postfix Form) The same procedure is to be applied to convert infix into prefix except that during conversion of a single operation, the operator is placed before the two operands. Let's take the same example and convert it to Prefix Notation. :: A + B / C (First Convert B / C -> / B C) 1: A + / B C (Next Operation is A + (/BC) -> + A /BC + 2: + A / B C Sometimes, an expression contains parenthesis like this: A + B * ( C + D ) Parenthesis are used to force a given priority to the expression that it encloses. In this case, C+D is calculated first, then multiplied to B and then added to A. Without the parenthesis, B * C would have been evaluated first. To convert an expression with paranthesis, we first convert all expressions that are enclosed within the simple brackets like this: [INFIX TO POSTFIX] :: A + B * ( C + D ) 1: A + B * C D + 2: A + B C D + * 3: A B C D + * + Once an expression has been converted into postfix or prefix, there is no need to include the parenthesis since the priority of operations is already taken care of in the final expression. IMPORTANT: Keep in mind that converting this expression back to infix would result in the same original infix expression without the paranthesis, which would ruin the result of the expression. Only the Prefix and Postfix forms are capable of preserving the priority of operations and are hence used for evaluating expressions instead of infix. IV. CONVERSION TECHNIQUES Now that you know what infix, prefix and postfix operations are, let us see how we can programmatically convert expressions from one form into another. This can be done by various methods but I'll be explaining the two most common techniques: 1) USING STACKS 2) USING Expression TREES Let us study the first technique. IV.A CONVERSION USING STACKS I shall be demonstrating this technique to convert an infix expression to a postfix expression. In this method, we read each character one by one from the infix expression and follow a certain set of steps. The Stack is used to hold only the operators of the expression. This is required to ensure that the priority of operators is taken into consideration during conversion. Before you take a look at the code, read the Algorithm given below so that you can concentrate on the technique rather than the C code. It will be much easier to comprehend the code once you know what it is supposed to do. The algorithm below does not follow any specific standard Here's the Algorithm to the Infix to Prefix Convertor Function: 01 Algorithm infix2postfix(infix expression string, postfix expression string) 02 { 03 char *i,*p; 04 05 i = first element in infix expression 06 p = first element in postfix expression 07 08 while i is not null 09 { 10 while i is a space or tab 11 { 12 increment i to next character in infix expression; 13 } 14 15 if( i is an operand ) 16 { 17 p = i; 18 increment i to next character in infix expression; 19 increment p to next character in postfix expression; 20 } 21 22 if( i is '(' ) 23 { 24 stack_push(i); 25 increment i to next character in infix expression; 26 } 27 28 if( i is ')' ) 29 { 30 while( element at top of stack != '(' ) 31 { 32 p = element at top of stack; 33 increment p to next character in postfix expression; 34 } 35 increment i to next character in infix expression; 36 } 37 38 if( i is an operator ) 39 { 40 if( stack is empty ) 41 stack_push(i); 42 else 43 { 44 45 while priority(element at top of stack) >= priority(i) 46 { 47 p = element at top of stack; 48 increment p to next character in postfix expression; 49 } 50 stack_push(i); 51 } 52 increment i to next character in infix expression; 53 } 54 } 55 while stack is not empty 56 { 57 p = stack_pop() 58 increment p to next character in postfix expression; 59 } 60 p = ''; 61 } Try converting an infix expression A + B / C to postfix on paper using the above algorithm and check if you're getting the correct result. Now you can see how the above algorithm is implemented in C. In the following C code, I have added a 'whitespace adder' feature to the infix2postfix() function. If the third parameter is 0, A + B / C will be converted as ABC/+ If the third parameter is 1, A + B / C will be converted as A B C / + This doesn't seem like a big deal, does it? But in actual practice we will be dealing with numbers as well. Which means that 32 + 23 would be converted to 3223+. This could mean 3 + 223, 32 + 23 or 322 +3. Hence to prevent such cases, pass 1 as the third parameter to get 32 23 +. Here's the Code: 001 #include 002 #include 003 #include 004 005 #define MAX 10 006 #define EMPTY -1 007 008 struct stack 009 { 010 char data[MAX]; 011 int top; 012 }; 013 014 int isempty(struct stack *s) 015 { 016 return (s->top == EMPTY) ? 1 : 0; 017 } 018 019 void emptystack(struct stack* s) 020 { 021 s->top=EMPTY; 022 } 023 024 void push(struct stack* s,int item) 025 { 026 if(s->top == (MAX-1)) 027 { 028 printf(" STACK FULL"); 029 } 030 else 031 { 032 ++s->top; 033 s->data[s->top]=item; 034 } 035 } 036 037 char pop(struct stack* s) 038 { 039 char ret=(char)EMPTY; 040 if(!isempty(s)) 041 { 042 ret= s->data[s->top]; 043 --s->top; 044 } 045 return ret; 046 } 047 048 void display(struct stack s) 049 { 050 while(s.top != EMPTY) 051 { 052 printf(" %d",s.data[s.top]); 053 s.top--; 054 } 055 } 056 057 int isoperator(char e) 058 { 059 if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%') 060 return 1; 061 else 062 return 0; 063 } 064 065 066 int priority(char e) 067 { 068 int pri = 0; 069 070 if(e == '*' || e == '/' || e =='%') 071 pri = 2; 072 else 073 { 074 if(e == '+' || e == '-') 075 pri = 1; 076 } 077 return pri; 078 } 079 080 void infix2postfix(char* infix, char * postfix, int insertspace) 081 { 082 char *i,*p; 083 struct stack X; 084 char n1; 085 emptystack(&X); 086 i = &infix[0]; 087 p = &postfix[0]; 088 089 while(*i) 090 { 091 while(*i == ' ' || *i == ' ') 092 { 093 i++; 094 } 095 096 if( isdigit(*i) || isalpha(*i) ) 097 { 098 while( isdigit(*i) || isalpha(*i)) 099 { 100 *p = *i; 101 p++; 102 i++; 103 } 104 /*SPACE CODE*/ 105 if(insertspace) 106 { 107 *p = ' '; 108 p++; 109 } 110 /*END SPACE CODE*/ 111 } 112 113 if( *i == '(' ) 114 { 115 push(&X,*i); 116 i++; 117 } 118 119 if( *i == ')') 120 { 121 n1 = pop(&X); 122 while( n1 != '(' ) 123 { 124 *p = n1; 125 p++; 126 /*SPACE CODE*/ 127 if(insertspace) 128 { 129 *p = ' '; 130 p++; 131 } 132 /*END SPACE CODE*/ 133 n1 = pop(&X); 134 } 135 i++; 136 } 137 138 if( isoperator(*i) ) 139 { 140 if(isempty(&X)) 141 push(&X,*i); 142 else 143 { 144 n1 = pop(&X); 145 while(priority(n1) >= priority(*i)) 146 { 147 *p = n1; 148 p++; 149 /*SPACE CODE*/ 150 if(insertspace) 151 { 152 *p = ' '; 153 p++; 154 } 155 /*END SPACE CODE*/ 156 n1 = pop(&X); 157 } 158 push(&X,n1); 159 push(&X,*i); 160 } 161 i++; 162 } 163 } 164 while(!isempty(&X)) 165 { 166 n1 = pop(&X); 167 *p = n1; 168 p++; 169 /*SPACE CODE*/ 170 if(insertspace) 171 { 172 *p = ' '; 173 p++; 174 } 175 /*END SPACE CODE*/ 176 } 177 *p = ''; 178 } 179 180 int main() 181 { 182 char in[50] = { 0 },post[50] = { 0 }; 183 184 iprintf("Enter Infix Expression : "); 185 186 fgets(in, sizeof(in), stdin); 187 in[strlen(in) - 1] = ''; 188 infix2postfix(&in[0],&post[0],1); 189 printf("Postfix Expression is : %s ",&post[0]); 190 191 return 0; 192 } 193 /* SAMPLE OUTPUT: 194 Enter Infix Expression : A + B + C / (E - F) 195 Postfix Expression is : A B + C E F - / + 196 */ Now try writing a program to convert infix to prefix as an exercise. IV.B CONVERSION USING Expression TREES Expression Trees are a slight variation of a Binary Tree in which every node in an expression tree is an element of an expression. It is created in such a way that an inorder traversal would result in an infix expression, preorder in prefix and postorder in postfix. The main advantages of an expression tree over the previous technique are pretty obvious, easier evaluation procedures and efficiency. The evaluation procedure of both the conversion techniques will be discussed in the next section. The previous technique gives the resultant postfix expression as a string. If we now wish to convert the resultant postfix expression into prefix, we must pass the entire string to another (long) function which would provide the result into another string. If at any given point we wish to have all three forms of an expression, we would need three strings (of outrageously long lengths for longer expressions) whereas if we use an Expression Tree, we don't need anything else. We can choose which expression we want by choosing the appropriate traversal method. In short, unlike a string an Expression Tree can be interpreted as either infix, postfix or prefix without changing the structure of the tree. Consider an Infix expression : A + B / C This expression would be represented in an Expression Tree as follows: Quote {+} (ROOT) | | --- --- | | {A} {/} | | --- --- | | {B} {C} Let us Traverse this Expression Tree in Inorder, Preorder and Postorder. Inorder : A + B / C Preorder : + A / B C Postorder : A B C / + As you can see, Inorder Traversal gives us the Infix expression, Preorder the Prefix expression and Postorder gives the Postfix expression. Isn't this amazing? We don't even need a (long and complicated) conversion technique!! The only thing that we need to do is convert an expression string into an Expression Tree. This procedure is somewhat complex and requires a Stack as well. This time I will demonstrate this technique to convert a Postfix Expression to an Expression Tree. Here's the algorithm for converting a postfix expression string to an Expression Tree. 01 Algorithm postfix2exptree(postfix string, root) 02 { 03 NODES newnode,op1,op2; 04 05 p = first element in postfix expression; 06 while(p is not null) 07 { 08 while(p is a space or a tab) 09 { 10 increment p to next character in postfix expression; 11 } 12 13 if( p is an operand ) 14 { 15 newnode = ADDRESS OF A NEW NODE; 16 newnode->element = p; 17 newnode->left = NULL; 18 newnode->right = NULL; 19 stack_push(newnode); 20 } 21 else 22 { 23 op1 = stack_pop(); 24 op2 = stack_pop(); 25 newnode = ADDRESS OF A NEW NODE; 26 newnode->element = p; 27 newnode->left = op2; 28 newnode->right = op1; 29 stack_push(newnode); 30 } 31 increment p to next character in postfix expression; 32 } 33 root = stack_pop(); 34 } After the function is finished with execution, the root pointer would point to the root node of the expression tree. Once again I'd like you to create an expression tree of A B C * + using the above algorithm on paper to understand how it works. And finally, the implementation in C: 001 #include 002 #include 003 #include 004 005 #define MAX 10 006 #define EMPTY -1 007 008 009 struct node 010 { 011 char element; 012 struct node *left,*right; 013 }; 014 015 struct stack 016 { 017 struct node *data[MAX]; 018 int top; 019 }; 020 021 int isempty(struct stack *s) 022 { 023 return (s->top == EMPTY) ? 1 : 0; 024 } 025 026 void emptystack(struct stack* s) 027 { 028 s->top=EMPTY; 029 } 030 031 void push(struct stack* s, struct node *item) 032 { 033 if(s->top == (MAX-1)) 034 { 035 printf(" STACK FULL"); 036 } 037 else 038 { 039 ++s->top; 040 s->data[s->top]=item; 041 042 } 043 } 044 045 struct node* pop(struct stack* s) 046 { 047 struct node *ret=NULL; 048 if(!isempty(s)) 049 { 050 ret= s->data[s->top]; 051 --s->top; 052 } 053 return ret; 054 } 055 056 void postfix2exptree(char* postfix, struct node **root) 057 { 058 struct stack X; 059 struct node *newnode,*op1,*op2; 060 char *p; 061 p = &postfix[0]; 062 emptystack(&X); 063 while(*p) 064 { 065 066 while(*p == ' ' || *p == ' ') 067 { 068 p++; 069 } 070 071 if(isalpha(*p) || isdigit(*p)) 072 { 073 newnode = malloc(sizeof(struct node)); 074 newnode->element = *p; 075 newnode->left = NULL; 076 newnode->right = NULL; 077 push(&X,newnode); 078 } 079 else 080 { 081 op1 = pop(&X); 082 op2 = pop(&X); 083 newnode = malloc(sizeof(struct node)); 084 newnode->element = *p; 085 newnode->left = op2; 086 newnode->right = op1; 087 push(&X,newnode); 088 } 089 p++; 090 } 091 *root = pop(&X); 092 } 093 094 void inorder(struct node *x) 095 { 096 if(x != NULL) 097 { 098 inorder(x->left); 099 printf("%c ",x->element); 100 inorder(x->right); 101 } 102 } 103 104 void preorder(struct node *x) 105 { 106 if(x != NULL) 107 { 108 printf("%c ",x->element); 109 preorder(x->left); 110 preorder(x->right); 111 } 112 } 113 114 void postorder(struct node *x) 115 { 116 if(x != NULL) 117 { 118 postorder(x->left); 119 postorder(x->right); 120 printf("%c ",x->element); 121 } 122 } 123 124 int main() 125 { 126 struct node *r; 127 postfix2exptree("A B C * +",&r); 128 printf("Inorder = "); 129 inorder®; 130 printf(" Preorder = "); 131 preorder®; 132 printf(" Postorder = "); 133 postorder®; 134 return 0; 135 } 136 /* OUTPUT: 137 Inorder = A + B * C 138 Preorder = + A * B C 139 Postorder = A B C * + 140 */ As you can see, once the expression tree is built, the expression can be converted to any of the three forms by using an appropriate traversal method. I hope you can now understand its true advantage. In this case since we were only dealing with alphabets (as variables in the expression), we chose a node structure like this: 1 struct node 2 { 3 char element; 4 struct node *left,*right; 5 }; But in practice, we will be dealing with numbers (which will be more than a character in length is stored as a set of characters). Hence we would need two extra variables in the structure to hold the operator and the number as well as another flag variable which states whether the node contains an element or an operator. Hence the structure would look like this: 1 struct node 2 { 3 char kind; 4 char op; 5 int number; /* even float would do */ 6 struct node *left,*right; 7 }; In this structure, if the node is to store an operator, it would store it in the op variable. If the node is required to store a number, it would do so in the number variable. If the node contains an operator the kind variable would have the value 'O' (or anything you wish) and 'N' for a number. Take care not to name the op variable as operator since this will lead to compilation errors if compiled on a C++ compiler. C++ compilers won't compile the code since operator is a keyword in the C++ Language. Not many people (today) use Pure C Compilers to compile C code (you're probably using a C++ Compiler right now too), it's best to avoid renaming it as operator. I have chosen a char data type since it consumes only 1 byte rather than 2/4 bytes for an int for 16/32-bit based programes. This would reduce the size of the structure by 3 bytes. Since we're on the topic of efficiency, there is another improvement that we can make to the structure definition. Each Node in an expression tree can hold either an operator or a number, but not both. Hence if an operator is stored in a node, 2/4 bytes of space is wasted for the unused 'number' variable. If a node holds a number, there is a wastage of 1 byte for the unused op variable. How can we improve upon this structure design? The answer is Unions. Unions are user-defined data types that can contain only one data element at a given time. The members of a union represent the kinds of data the union can contain. An object of union type requires enough storage to represent each member and hence its size is the same size of the largest member in its member-list. This is what the improved structure definition looks like: 01 struct node 02 { 03 char kind; 04 union element 05 { 06 char op; 07 int number; 08 }; 09 struct node *left, *right; 10 }; This is an ideal situation for using a union. As an exercise, try to write a function that builds an expression tree for infix and prefix expression strings using the node structure that uses unions. V. EVALUATION TECHNIQUES The Evaluation process is the easiest part of an expression evaluator. Unlike the conversion process, evaluation functions are relatively small and easy to understand (and even write ;) ) This is because now, we don't have to worry about the priority of operations anymore. Remember that evaluation of an expression is always performed on prefix or postfix expressions and never infix (this should be obvious by now). As usual, I'll be dividing this section into two sub-parts. V.A : EVALUATING Expression STRINGS V.B : EVALUATING Expression TREES V.A EVALUATING Expression STRINGS It is fairly simple to evaluate postfix/prefix expression strings. The algorithm for evaluating a postfix expression is given below: 01 Algorithm evaluate(postfix expression string) 02 { 03 while current character in postfix string is not null 04 { 05 x = next character in postfix string; 06 07 if( x is an operand ) 08 stack_push(x); 09 else 10 { 11 op1 = stack_pop(); 12 op2 = stack_pop(); 13 result = op2 op1; 14 stack_push(result); 15 } 16 } 17 18 result = stack_pop(); 19 return result; 20 } Simple isn't it? Let us see it in action: 001 #include 002 #include 003 004 #define MAX 50 005 #define EMPTY -1 006 007 struct stack 008 { 009 int data[MAX]; 010 int top; 011 }; 012 013 void emptystack(struct stack* s) 014 { 015 s->top = EMPTY; 016 } 017 018 void push(struct stack* s,int item) 019 { 020 if(s->top == (MAX-1)) 021 { 022 printf(" STACK FULL"); 023 } 024 else 025 { 026 ++s->top; 027 s->data[s->top]=item; 028 } 029 } 030 031 int pop(struct stack* s) 032 { 033 int ret=EMPTY; 034 if(s->top == EMPTY) 035 printf(" STACK EMPTY"); 036 else 037 { 038 ret= s->data[s->top]; 039 --s->top; 040 } 041 return ret; 042 } 043 044 void display(struct stack s) 045 { 046 while(s.top != EMPTY) 047 { 048 printf(" %d",s.data[s.top]); 049 s.top--; 050 } 051 } 052 053 int evaluate(char *postfix) 054 { 055 char *p; 056 struct stack stk; 057 int op1,op2,result; 058 059 emptystack(&stk); 060 p = &postfix[0]; 061 062 while(*p != '') 063 { 064 /* removes tabs and spaces */ 065 while(*p == ' ' || *p == ' ') 066 { 067 p++; 068 } 069 /* if is digit */ 070 if(isdigit(*p)) 071 { 072 push(&stk,*p - 48); 073 } 074 else 075 { 076 /* it is an operator */ 077 op1 = pop(&stk); 078 op2 = pop(&stk); 079 080 switch(*p) 081 { 082 case '+': 083 result = op2 + op1; 084 break; 085 086 case '-': 087 result = op2 - op1; 088 break; 089 090 case '/': 091 result = op2 / op1; 092 break; 093 094 case '*': 095 result = op2 * op1; 096 break; 097 098 case '%': 099 result = op2 % op1; 100 break; 101 102 default: 103 printf(" Invalid Operator"); 104 return 0; 105 } 106 push(&stk,result); 107 } 108 p++; 109 } 110 result = pop(&stk); 111 return result; 112 } 113 114 int main() 115 { 116 char exp[MAX]; 117 printf("Enter Postfix Expression : "); 118 fgets(exp, sizeof(exp), stdin); 119 exp[strlen(exp) - 1] = ''; 120 printf("%s EQUALS %d ",exp,evaluate(&exp[0])); 121 return 0; 122 } 123 /* SAMPLE OUTPUT: 124 Enter Postfix Expression : 3 5 + 2 / 125 3 5 + 2 / EQUALS 4 126 */ Now try writing an evaluator function for prefix expressions. V.B EVALUATING Expression TREES Expression trees are usually evaluated using recursion. The Recursive Evaluator is extremely simple. Here is the Algorithm: 01 Algorithm evaluatetree(Node x) 02 { 03 if( x is an operator ) 04 { 05 op1 = evaluatetree(x.left); 06 op2 = evaluatetree(x.right); 07 result = op1 op2; 08 } 09 else 10 return result; /* x is a number */ 11 } That's It!!! And there's no need to write two separate functions for postfix and prefix expressions. Here's the Algorithm implemented in C code: 001 #include 002 #include 003 #include 004 #include 005 006 #define MAX 10 007 #define EMPTY -1 008 009 struct node 010 { 011 char kind; 012 char op; 013 int number; 014 struct node *left,*right; 015 }; 016 017 struct stack 018 { 019 struct node *data[MAX]; 020 int top; 021 }; 022 023 int isempty(struct stack *s) 024 { 025 return (s->top == EMPTY) ? 1 : 0; 026 } 027 028 void emptystack(struct stack* s) 029 { 030 s->top=EMPTY; 031 } 032 033 void push(struct stack* s, struct node *item) 034 { 035 if(s->top == (MAX-1)) 036 { 037 printf(" STACK FULL"); 038 } 039 else 040 { 041 ++s->top; 042 s->data[s->top]=item; 043 044 } 045 } 046 047 struct node* pop(struct stack* s) 048 { 049 struct node *ret=NULL; 050 if(!isempty(s)) 051 { 052 ret= s->data[s->top]; 053 --s->top; 054 } 055 return ret; 056 } 057 058 void postfix2exptree(char* postfix, struct node **root) 059 { 060 struct stack X; 061 struct node *newnode,*op1,*op2; 062 char numberextract[5]; 063 char *p; 064 065 emptystack(&X); 066 p = &postfix[0]; 067 strcpy(numberextract,""); 068 while(*p) 069 { 070 071 while(*p == ' ' || *p == ' ') 072 { 073 p++; 074 } 075 076 if(isdigit(*p)) 077 { 078 while(isdigit(*p)) 079 { 080 strcat(numberextract,p); 081 p++; 082 } 083 084 newnode = malloc(sizeof(struct node)); 085 newnode->kind = 'N'; 086 newnode->number = atoi(numberextract); 087 newnode->left = NULL; 088 newnode->right = NULL; 089 push(&X,newnode); 090 strcpy(numberextract,""); 091 } 092 else 093 { 094 op1 = pop(&X); 095 op2 = pop(&X); 096 newnode = malloc(sizeof(struct node)); 097 newnode->kind = 'O'; 098 newnode->op = *p; 099 newnode->left = op2; 100 newnode->right = op1; 101 push(&X,newnode); 102 } 103 p++; 104 } 105 *root = pop(&X); 106 } 107 108 int evaluatetree(struct node *x) 109 { 110 if( x->kind == 'O' ) 111 { 112 int op1 = evaluatetree( x->left ); 113 int op2 = evaluatetree( x->right ); 114 switch ( x->op ) 115 { 116 case '+': return op1 + op2; 117 case '-': return op1 - op2; 118 case '*': return op1 * op2; 119 case '/': return op1 / op2; 120 default: return 0; 121 } 122 } 123 else 124 return (x->number); 125 } 126 127 void inorder(struct node *x) 128 { 129 if(x != NULL) 130 { 131 inorder(x->left); 132 133 if(x->kind == 'O') 134 printf("%c ",x->op); 135 else 136 printf("%d ",x->number); 137 138 inorder(x->right); 139 } 140 } 141 142 void preorder(struct node *x) 143 { 144 if(x != NULL) 145 { 146 if(x->kind == 'O') 147 printf("%c ",x->op); 148 else 149 printf("%d ",x->number); 150 151 preorder(x->left); 152 preorder(x->right); 153 } 154 } 155 156 void postorder(struct node *x) 157 { 158 if(x != NULL) 159 { 160 postorder(x->left); 161 postorder(x->right); 162 163 if(x->kind == 'O') 164 printf("%c ",x->op); 165 else 166 printf("%d ",x->number); 167 } 168 } 169 170 int main() 171 { 172 struct node *r; 173 postfix2exptree("100 50 - 2 /",&r); 174 printf("Inorder = "); 175 inorder®; 176 printf(" Preorder = "); 177 preorder®; 178 printf(" Postprder = "); 179 postorder®; 180 printf(" Result = %d ",evaluatetree®); 181 return 0; 182 } 183 /* OUTPUT: 184 Inorder = 100 - 50 / 2 185 Preorder = / - 100 50 2 186 Postprder = 100 50 - 2 / 187 Result = 25 188 */ Since I can't ask you to write an prefix version of the evaluator, write the same program using unions in the node structure as an exercise. (Thought you could get away with it this time eh?) ;) VI. IMPROVEMENTS AND APPLICATIONS You should now have a basic idea about converting and evaluating arithmetic expressions in C. You can add a lot of improvements by further adding support for more operators and functions such as sin(), cos(), log() etc in expressions. This is a little complicated but not as difficult as it may seem. Simply assign a token to each function (like a single character 'S' for sine) and test for the token during evaluation and perform the appropriate function. The whole idea of this tutorial is to give you an understanding of how arithmetic expressions are calculated by computers and embedded systems. Don't reinvent the wheel by writing your own expression evaluators while writing programs. Languages such as C/C++,Java,C# etc. have in-built or external libraries that contain expression evaluators. Infact, using these libraries is recommended as they are more efficient and are less likely to be bugged. Casio Scientific Calculators and many more use such techniques to solve arithmetic expressions. If you own a Casio fx-XXX MS/ES Series Calculator, you can even see that a stack is being internally used (I currently use a Casio fx-991 ES). If you key in a long expression with loads of operators and parenthesis and press the '=' key, you will get a "Stack Error" or "Stack Full" Error. Compilers also compute expressions using these techniques too. Almost every mathematical program makes use of this too (Eg. Mathematica and MATLAB)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.