Help with C++ 16.10 Homework 6a Shunting Yard Stacks and Queues are data structu
ID: 3700908 • Letter: H
Question
Help with C++
16.10 Homework 6a Shunting Yard Stacks and Queues are data structures that organize the storage and retrieval of items. A stack is a Last-In-First-Out (LIFO) data structure, like a stack of plates on a table, while a queue is First-In-First-Out (FIFO), like a line at a movie theater. Both of these structures are used extensively in many contexts. This assignment will give you some experience working with these two data structures. Related HackerRank Problems o C++->Introduction-> variable-sized-arrays o Data Structures -> Stacks->Balanced Brackets o Data Structures->Queues->Truck Tour Problem 6a:Shunting Yard Algorithm The "Shunting yard" algorithm (https://en.wikipedia.org/wiki/Shunting-yard_algorithm) is a stack-based method to convert an in-fix expression such as 3+4)* 12 2 to postfix 3 4 12* 2 . The algorithm relies on a stack of operators (+-18) to work. A simplified version of the algorithm can be stated as followsExplanation / Answer
#include<bits/stdc++.h>
using namespace std;
bool isOperator(string s){
return ( s=="+" || s=="-" || s=="*" || s=="/" || s=="%" );
}
int precedence(string op){
if( op=="+" || op=="-" ) return 1;
if( op=="*" || op=="/" || op=="%" ) return 2;
return -1;
}
int main(){
cout<<"Enter an infix expression : ";
string in,out;//out will have ouput postfix expression
stack<string> stk;//stack for storing operators and opening bracket
getline(cin,in);
//we have taken infix expression as input in string variable in
int n=in.size(),i=0;
//now we will be processing the infix expression
/*
* now we will parse the infix expression
* we know that every element in the infix expression is separated by atleast one space (means greater than 1 space)
*
*/
out="";
while(i<n){
//this piece of code will get executed if there are more than one space
if(in[i]==' '){
i++;
continue;
}
//clearly our control flow reached here that means we don't have space this time, it is the starting character of an operator, operand or simply a bracket
int j=i;
string s="";
while(j<n && in[j]!=' '){
s=s+in[j];
j++;
}
i=j;
//we have the operand, operator or bracket which is stored in s
if(s=="("){
stk.push(s);
//if input is opening bracket,add it to the stack
}else if(s==")"){
while(!stk.empty()){
string peek=stk.top();
stk.pop();
if(peek=="(")break;
out=out+peek+" ";
}
if(!stk.empty() && stk.top() =="("){
//we have an imbalanced bracket here
//we have an extra opening bracket here
cout<<"Invalid infix expression ";
return -1;
}
//if input is closing bracket,we need to pop out everything from stack until we encounter an opening bracket
}else if(isOperator(s)){
while(!stk.empty() && precedence(s)<=precedence(stk.top())){
string peek=stk.top();
stk.pop();
out=out+peek+" ";
}
stk.push(s);
//if it is an operator then we need to pop out everything until we encounter an operator of low priority
}else{
//s is an operand
out=out+s+" ";
}
}
//print rest of the stack
while(!stk.empty()){
string peek=stk.top();
stk.pop();
out=out+peek+" ";
}
cout<<"Postfix expression : "<<out<<endl;//printing output postfix expression
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.