Study Sheet Step by Step 1. Consider the following algorithm X is an arithmetic
ID: 3880321 • Letter: S
Question
Study Sheet
Step by Step
1. Consider the following algorithm X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y. (1)Push [ onto Stack, and add ] to the end of X. (2)Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty. (3)If ( is encountered, push it onto Stack. (4)If an operator is encountered, then: Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator. Add operator to Stack. (5)If a ) or ] is encountered, then: Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a respective ( or [ is encountered. Remove the ( or [ from Stack. (6)If an operand is encountered, add it to Y. (7)END.
2. First make sure you understand the algorithm by converting the string (A+B)*C(D/(J+D)) to postfix. (1)Now write a function infix-to-postfix that accepts an infix expression (string) and returns a string containing the expression in postfix. (3)Test your program on the string (A+B)*C-(D/(J+D)) by writing a main program.
You will need the Stack class for step 2 on problem number 2. Here it is below.
Explanation / Answer
#include<bits/stdc++.h>
using namespace std;
//function to find the precedence of operators
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
string infix_to_postfix(string s)
{
string result;
std::stack<char> stack;
stack.push('z'); // to avoid runtime error push some character for checking the empty condition and do not use empty() function
int l = s.length();
for(int i = 0; i < l; i++)
{
// if the scanned character is an operand, add it to output string.
if((s[i] >= 'A' && s[i] <= 'Z')|| (s[i] >= 'a' && s[i] <= 'z'))
result+=s[i];
// if the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is found.
else if(s[i] == ')')
{
while(stack.top()!='z' && stack.top() != '(')
{
char c = stack.top();
result += c;
stack.pop();
}
if (stack.top()!='z' && stack.top() != '(')
return "Invalid Expression"; // invalid expression
else
stack.pop();
}
// if the scanned character is an ‘(‘, push it to the stack.
else if(s[i] == '(')
stack.push('(');
// an operator is scanned
else{
while(precedence(s[i]) <= precedence(stack.top()) && (!stack.empty()))
{
char c = stack.top();
result += c;
stack.pop();
}
stack.push(s[i]);
}
}
//pop all the remaining elements from the stack
while(stack.top()!='z')
{
char c = stack.top();
result += c;
stack.pop();
}
return result;
}
// main function to test the infix_to_postfix function
int main()
{
string s = "(A+B)*C(D/(J+D))";
s=infix_to_postfix(s);
cout << s << endl;
return 0;
}
Output of the program is : AB+CDJD+/*