1. Programming with Stacks Write a program that uses Stacks to determine if a li
ID: 3760710 • Letter: 1
Question
1. Programming with Stacks
Write a program that uses Stacks to determine if a line written with parentheses is well-formed or not. This is a subtask similar to what compilers use to determine if you are missing (or have too many) curly braces or parentheses or brackets.
The program should read the user input, and should push an open ( when it is encountered, and perform a pop when a closed ) is encountered.
This way, if at the end of the program run, the stack is empty, then the line is well-formed.
If the end of the input is reached and the stack is not empty, that means there were too many open parentheses, (.
If at any time, the program sees a closed parenthesis, ), and the stack is empty already, then an exception will be thrown and this is an indicator that there are too many, or at least a misplaced, closed parenthesis.
Either situation should cause the program to indicate it is not well formed.
An example run might look like the following:
Please input a set of parentheses
()(())(())
--> Input is well-formed
Another example run might look like the following:
Please input a set of parentheses
)(())(())
--> Sorry, input is NOT well-formed
2. Tree Questions
2.1 Is this tree a binary search tree?
2.2 What is the inorder traversal of the tree?
2.3 What is the postorder traversal of the tree?
2.4 What is the preorder traversal of the tree?
2.5 What is the height of the tree?
Please input a set of parentheses
()(())(())
--> Input is well-formed
64 70 24Explanation / Answer
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// function checks if opening and closing brackets are same
bool bracketsame(char open,char close)
{
if(open == '(' && close == ')') return true;
else if(open == '{' && close == '}') return true;
else if(open == '[' && close == ']') return true;
else
return false;
}
bool wellFormedparantheses(string exp)
{
stack<char> S;
for(int i =0;i<exp.length();i++)
{
if(exp[i] == '('|| exp[i] == '{' || exp[i] == '[' )
S.push(exp[i]);
else if(exp[i] == ')'|| exp[i] == '}' || exp[i] == ']')
{
if(S.empty() || !bracketsame(S.top(),exp[i]))
return false;
else
S.pop();
}
}
if(S.empty())
return true;
else
return false;
}
int main()
{
string exp;
cout<<"Please input a set of parentheses: ";
cin>>exp;
if(wellFormedparantheses(exp))
cout<<"--->Input is well-formed ";
else
cout<<"--->Sorry, input is NOT well-formed ";
}
// Please note you did not mention to code the answers for your second question. So I am giving direct answers.
2.1: Yes Tree is binary search Tree because Every node has max 2 childs and left chile is smaller and right child is greater than Parent node.
2.2. 21,22,24,33,56,64,70 ( In inorder root node is always in middle then left then right)
2.3 21,24,33,22,0,64,56 (in Post order Root node is always last. First left then right then root)
2.4 56,22,21,33,24,64,70 (in pre order Root is always first then left then right)
2.5 Height of tree is number of nodes from root to leaf node in longest path. So here height is 4(56-22-33-24).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.