1. Infix Notation:
Operators in infix notation are positioned between the operands they act upon.
For example: 5 + 8
In computer programming, infix expressions pose a greater challenge due to the complexity of determining operator precedence. Programmers usually input expressions in infix notation, mirroring how humans naturally write, read, and interpret them. To simplify analysis, these expressions are commonly converted into either postfix or prefix notation.
The result of this function is a queue that holds the modified expression converted to postfix notation from an initial infix expression. There is a potential to adjust the method to produce the result of evaluating the expression instead of a queue. The key lies in employing two stacks instead of one: one stack for operators and the other for operands.
In C programming, infix notation is the conventional method for expressing mathematical formulas, where operators are positioned between operands. Below is a fundamental mathematical operation illustrated using infix notation:
Example:
Example
#include <stdio.h>
int main()
{
int a = 7;
int b = 8;
int result;
// Addition using infix notation
result = a + b;
printf("Addition of %d and %d is: %d\n",a,b,result);
// Subtraction using infix notation
result = a - b;
printf("Subtraction of %d and %d is: %d\n",a,b,result);
// Multiplication using infix notation
result = a * b;
printf("Multiplication of %d and %d is: %d\n",a,b,result);
// Division using infix notation
result = a / b;
printf("Division of %d and %d is: %d\n",a,b,result);
return 0;
}
Output:
Output
Addition of 7 and 8 is: 15
Subtraction of 7 and 8 is: -1
Multiplication of 7 and 8 is: 56
Division of 7 and 8 is: 0
Explanation:
Declare two integer variables, a and b, and perform various arithmetic operations on them using the operators +, -, *, and /. The output of the calculations is displayed on the console.
2. Prefix Notation:
In the prefix notation, operators are written before the operands . In prefix notation, also referred to as Polish notation , each operator is followed by each of its operands . To put it another way, the operator comes before its operands . Because the position of the operator controls which operands it operates upon, this notation does away with the requirement for brackets to denote the order of operations. The Polish mathematician Jan Ukasiewicz created the prefix notation, which is employed in a variety of mathematics and computer science situations.
- In front of their operands , operators are positioned.
- The operator's position clearly defines its operands . Thus, there are no ambiguities regarding the order of operations.
- Usually, a stack-based technique is used to analyze prefix expressions.
- For instance, think about the infix equation "2 + 3" . The format for prefixes is "+ 2 3" . The breakdown of this phrase is as follows:
- Before the operands "2" and "3" , the operator "+" is present, signifying addition.
- To begin evaluating this expression, add the "+" operator to the operands "2" and "3" , which will give you the number "5" .
The following steps can be used to evaluate a prefix expression in C while using a stack data structure:
- Create an empty stack at first.
- The expression should be read from left to right .
- About each operand or operator:
- Put it on the stack if it is an operand.
If it functions as an operator, eliminate the required number of operands from the stack, perform the operation, and subsequently add the result back onto the stack.
Once the entire expression has been executed, the stack will contain solely the ultimate outcome.
Example:
Let's consider an example of converting an infix expression to a prefix expression in the C programming language:
Example
#include<string.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
struct Stack
{
int top;
int maxSize;
int *array;
};
struct Stack *create (int max)
{
struct Stack *stack = (struct Stack *) malloc (sizeof (struct Stack));
stack->maxSize = max;
stack->top = -1;
stack->array = (int *) malloc (stack->maxSize * sizeof (int));
return stack;
}
int isFull (struct Stack *stack)
{
if (stack->top == stack->maxSize - 1)
{
printf ("Will not be able to push maxSize reached\n");
}
return stack->top == stack->maxSize - 1;
}
int isEmpty (struct Stack *stack)
{
return stack->top == -1;
}
void push (struct Stack *stack, char item)
{
if (isFull (stack))
return;
stack->array[++stack->top] = item;
}
int pop (struct Stack *stack)
{
if (isEmpty (stack))
return INT_MIN;
return stack->array[stack->top--];
}
int peek (struct Stack *stack)
{
if (isEmpty (stack))
return INT_MIN;
return stack->array[stack->top];
}
int checkIfOperand (char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence (char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int getPostfix (char *expression)
{
int i, j;
struct Stack *stack = create (strlen (expression));
if (!stack)
return -1;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand (expression[i]))
expression[++j] = expression[i];
else if (expression[i] == '(')
push (stack, expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty (stack) && peek (stack) != '(')
expression[++j] = pop (stack);
if (!isEmpty (stack) && peek (stack) != '(')
return -1;
else
pop (stack);
}
else
{
while (!isEmpty (stack)
&& precedence (expression[i]) <= precedence (peek (stack)))
expression[++j] = pop (stack);
push (stack, expression[i]);
}
}
while (!isEmpty (stack))
expression[++j] = pop (stack);
expression[++j] = '\0';
}
void reverse (char *exp)
{
int size = strlen (exp);
int j = size, i = 0;
char temp[size];
temp[j--] = '\0';
while (exp[i] != '\0')
{
temp[j] = exp[i];
j--;
i++;
}
strcpy (exp, temp);
}
void brackets (char *exp)
{
int i = 0;
while (exp[i] != '\0')
{
if (exp[i] == '(')
exp[i] = ')';
else if (exp[i] == ')')
exp[i] = '(';
i++;
}
}
void InfixtoPrefix (char *exp)
{
int size = strlen (exp);
reverse (exp);
brackets (exp);
getPostfix (exp);
reverse (exp);
}
int main ()
{
printf ("The infix is: ");
char expression[] = "((a/b)+c)-(d+(e*f))";
printf ("%s\n", expression);
InfixtoPrefix (expression);
printf ("The prefix is: ");
printf ("%s\n", expression);
return 0;
}
Output:
Output
The infix is: ((a/b)+c)-(d+(e*f))
The prefix is: -+/abc+d*ef
Explanation:
- Struct Stack: The program specifies a structure called stack to describe a stack data structure. Several conversion-related activities make use of this stack.
- create function: Creating a stack is done using the create function . It allows space for the stack's array and sets its properties to initial values, including top, maxSize , and the array's contents .
- isFull and isEmpty Functions: Both isFull and isEmpty functions determine if the stack is full or empty . These functions are used by the program to prevent pushing components onto full stacks or popping elements off of empty stacks.
- push Function: The push function is used to add elements to the stack.
- pop Function: Using the pop function , you can remove items from a stack.
- peek Function: The peek function is used to retrieve the top element from a stack without deleting it.
- Function checkIfOperand: This function determines whether or not a character is an operand (a variable) . If the character is a letter ( uppercase or lowercase ), indicating an operand, it returns true .
- precedence Function: This function gives operators a precedence value. Greater values indicate greater precedence . It gives back the provided operator's precedence.
- getPostfix Function: The getPostfix function changes the infix expression's notation to postfix. The output is in postfix notation because it manages operators and brackets on the stack while iterating through the infix expression character by character.
- reverse Function: This function reverses the string that is passed to it. It is used to temporarily flip the infix phrase for convenience in converting to prefix notation.
- brackets Function: This function changes '(' to ')' and ')' to ')' in the given string. When converting to postfix notation , brackets are handled by this function.
- InfixtoPrefix Function: The fundamental logic for changing infix to prefix notation is included in the InfixtoPrefix method . It uses the function reverse to temporarily reverse the infix expression, brackets to handle brackets, getPostfix to convert to postfix notation , reverses the result back to prefix notation, etc.
- main Function: The program conducts the conversion from infix to prefix using the InfixtoPrefix function in the main function, which also contains an example infix phrase. A printout of the resulting prefix expression follows.
3. Postfix Notation:
Reverse Polish Notation (RPN), known as postfix notation as well, is a mathematical expression format in which each operator is placed after its operands. This means that the operator follows the operands in the expression. By using this notation, the need for brackets to indicate the sequence of operations is eliminated as the operator's position determines the operands it works with. Jan Usiewicz, a Polish mathematician, introduced postfix notation, which has become a common practice in the fields of computer science and calculator operations.
Postfix notation:
- Operators are positioned after their operands.
- There are no misunderstandings regarding the order of operations because the operator's location explicitly identifies its operands.
- Typically, a stack-based technique is used to evaluate postfix expressions .
- Take the infix statement "2 + 3" as an example. "2 3 +" is how it's expressed in postfix notation. An explanation of this phrase is provided below:
- The operands "2" and "3" are placed before the operator "+" .
- To evaluate this expression, you would start by adding the "+" operator to the operands "2" and "3" , which would give you the number "5" .
Utilizing a stack data structure and the general techniques below, you can evaluate a postfix expression in C.
- Create a new stack .
- Take a left-to-right reading of the expression .
- As an operator or an operand, each element is:
- Push it to the top of the stack if it's an operand.
- If it's an operator, remove the necessary number of operands off the stack, execute the operation, and then push the outcome back onto the stack.
- Once the entire expression has been processed, the only thing on the stack will be the final result .
Example:
Let's consider an illustration on converting infix notation to postfix notation in the C programming language:
Example
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define SIZE 100
char stack[SIZE];
int top = -1;
void push(char item)
{
if (top >= SIZE - 1)
{
printf("\nStack Overflow.");
}
else
{
top = top + 1;
stack[top] = item;
}
}
char pop()
{
char item;
if (top < 0)
{
printf("stack under flow: invalid infix expression");
getchar();
exit(1);
}
else
{
item = stack[top];
top = top - 1;
return (item);
}
}
int is_operator(char symbol)
{
if (symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol == '-')
{
return 1;
}
else
{
return 0;
}
}
int precedence(char symbol)
{
if (symbol == '^')
{
return (3);
}
else if (symbol == '*' || symbol == '/')
{
return (2);
}
else if (symbol == '+' || symbol == '-')
{
return (1);
}
else
{
return (0);
}
}
void InfixToPostfix(char infix_exp[], char postfix_exp[])
{
int i, j;
char item;
char x;
push('(');
strcat(infix_exp, ")");
i = 0;
j = 0;
item = infix_exp[i];
while (item != '\0')
{
if (item == '(')
{
push(item);
}
else if (isdigit(item) || isalpha(item))
{
postfix_exp[j] = item;
j++;
}
else if (is_operator(item) == 1)
{
x = pop();
while (is_operator(x) == 1 && precedence(x) >= precedence(item))
{
postfix_exp[j] = x;
j++;
x = pop();
}
push(x);
push(item);
}
else if (item == ')')
{
x = pop();
while (x != '(')
{
postfix_exp[j] = x;
j++;
x = pop();
}
}
else
{
printf("\nInvalid infix Expression.\n");
getchar();
exit(1);
}
i++;
item = infix_exp[i];
}
if (top > 0)
{
printf("\nInvalid infix Expression.\n");
getchar();
exit(1);
}
if (top > 0)
{
printf("\nInvalid infix Expression.\n");
getchar();
exit(1);
}
postfix_exp[j] = '\0';
}
int main()
{
char infix[SIZE], postfix[SIZE];
printf("ASSUMPTION: The infix expression contains single-letter variables and single digit constants only.\n");
printf("\nEnter Infix expression: ");
gets(infix);
InfixToPostfix(infix, postfix);
printf("Postfix Expression: ");
puts(postfix);
return 0;
}
Output:
Output
ASSUMPTION: The infix expression contains single-letter variables and single-digit constants only.
Enter Infix expression: 3+4-2*1/8
Postfix Expression: 34+21*8/-
Explanation:
- Stack Data Structure: The program makes use of an array-based stack to store operators transiently throughout the conversion process . The global array stack is used to implement the stack , and a variable of the integer type int top is used to track the entry at the top.
- push Function: Use the push function to add an item to the stack. Before pushing something, it looks for stack overflow .
- pop Function: Use the pop function to remove an item from the stack. Before returning the popped item, it checks for stack underflow .
- isoperator Function: The isoperator function checks whether the given character is an operator (, *, /, +, -) . If an operator, it gives back 1 ; otherwise, it gives back 0 .
- precedence Function: This function gives operators a precedence value. Greater values indicate greater precedence . It gives back the provided operator's precedence.
- InfixToPostfix Function: The fundamental component of the program is the InfixToPostfix function . It changes a postfix expression from an infix expression. The actions comprise: The infix expression is made easier to process by having a ' (' at the beginning and a ')' at the conclusion. Going through each letter in the infix expression in turn: It is immediately added to the postfix expression if it is an operand (a digit or a letter). It gets pushed onto the stack if it is an open parenthesis, "(" . If it's an operator, the program determines its precedence before adding operators from the stack to the postfix expression until it finds one with a lower precedence or an open parenthesis '(' . After that, it moves the active operator up onto the stack. If the parenthesis is close (')' , the program pops operators from the stack and adds them to the postfix expression until it reaches an open parenthesis ('(') , which is also popped from the stack. It checks for invalid infix expressions by making sure the stack is empty after processing all characters. The conversion was successful if the stack was empty. If not, it leaves after indicating an invalid infix expression.
- main Function: The user is prompted to input an infix expression in the main method . It is converted to postfix notation by using the InfixToPostfix After that, the final postfix expression is printed.
- The infix expression is made easier to process by having a ' (' at the beginning and a ')' at the conclusion.
- Going through each letter in the infix expression in turn:
- It is immediately added to the postfix expression if it is an operand (a digit or a letter).
- It gets pushed onto the stack if it is an open parenthesis, "(" .
- If it's an operator, the program determines its precedence before adding operators from the stack to the postfix expression until it finds one with a lower precedence or an open parenthesis '(' . After that, it moves the active operator up onto the stack.
- If the parenthesis is close (')' , the program pops operators from the stack and adds them to the postfix expression until it reaches an open parenthesis ('(') , which is also popped from the stack.
- It checks for invalid infix expressions by making sure the stack is empty after processing all characters. The conversion was successful if the stack was empty. If not, it leaves after indicating an invalid infix expression.