Write a C++ code for the following algorithm that convert from infix to postfix
ID: 3583481 • Letter: W
Question
Write a C++ code for the following algorithm that convert from infix to postfix
Write a C++ code for the following algorithm that convert from infix to postfix While (not end of imply) symb = next empty character if (symb is an operand) add symb to postfix string else while(! = empty (opstk)88 prcd (to p (opst K), symb) topsym = pop(opst k); add to sym to postfix string is if (Empty (opstk)!! symbol! =)) push (opst k, symb) else to P sym = pop (opst k); While (! Empty (opstk); to P sym = pop (opst K); add to symb to post fix string}Explanation / Answer
Postfix notation is also known as Reverse Polish Notation (RPN) in which every operator follows all of its operands.
Ex. (x+y) is expressed as xy+
the code is
=========================
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
/* The precedence function finds the precedence of the operators */
int precedence(char ch) {
switch (ch) {
case '/':
case '*': return 2;
case '+':
case '-': return 1;
default : return 0;
}
}
void infix2postfix(char infix[], char postfix[], int size) {
stack<char> s;
int weight;
int i = 0;
int k = 0;
char ch;
// iterate over the infix expression
while (i < size) {
ch = infix[i];
if (ch == '(') {
// push the opening parenthesis in stack
s.push(ch);
i++;
continue;
}
if (ch == ')') {
/* if we see a closing parenthesis,
pop of all the elements and append it to
the postfix expression till a opening parenthesis is encountered*/
while (!s.empty() && s.top() != '(') {
postfix[k++] = s.top();
s.pop();
}
// pop off the opening parenthesis also
if (!s.empty()) {
s.pop();
}
i++;
continue;
}
weight = precedence(ch);
if (weight == 0) {
// if operand append it to postfix expression
postfix[k++] = ch;
}
else {
if (s.empty()) {
// operator push the operator onto stack if
// stack is empty
s.push(ch);
}
else {
// pop of all the operators from the stack and
// append it to the postfix expression till we
// see an operator with a lower precedence that
// the current operator
while (!s.empty() && s.top() != '(' &&
weight <= precedence(s.top())) {
postfix[k++] = s.top();
s.pop();
}
// push the current operator onto stack
s.push(ch);
}
}
i++;
}
// pop of the remaining operators present in the stack
// and append it to postfix expression
while (!s.empty()) {
postfix[k++] = s.top();
s.pop();
}
postfix[k] = 0;
}
int main() {
char infix[] = "(x+y)";
int size = strlen(infix);
char postfix[size];
infix2postfix(infix,postfix,size);
cout<<" Infix Expression "<<infix;
cout<<" Postfix Expression "<<postfix;
cout<<endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.