Question: #include using namespace std; class Node{ private : char data; Node* nextNodePtr; Node* prevNodePtr; public : Node(){} void setData( char d){ data = d; }
#include
using namespace std;
class Node{
private:
char data;
Node* nextNodePtr;
Node* prevNodePtr;
public:
Node(){}
void setData(char d){
data = d;
}
char getData(){
return data;
}
void setNextNodePtr(Node* nodePtr){
nextNodePtr = nodePtr;
}
Node* getNextNodePtr(){
return nextNodePtr;
}
void setPrevNodePtr(Node* nodePtr){
prevNodePtr = nodePtr;
}
Node* getPrevNodePtr(){
return prevNodePtr;
}
};
class Stack{
private:
Node* headPtr;
Node* tailPtr;
public:
Stack(){
headPtr = new Node();
tailPtr = new Node();
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
Node* getHeadPtr(){
return headPtr;
}
Node* getTailPtr(){
return tailPtr;
}
bool isEmpty(){
if (headPtr->getNextNodePtr() == 0)
return true;
return false;
}
void push(char data){
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(0);
Node* lastNodePtr = tailPtr->getPrevNodePtr();
if (lastNodePtr == 0){
headPtr->setNextNodePtr(newNodePtr);
newNodePtr->setPrevNodePtr(0);
}
else{
lastNodePtr->setNextNodePtr(newNodePtr);
newNodePtr->setPrevNodePtr(lastNodePtr);
}
tailPtr->setPrevNodePtr(newNodePtr);
}
char pop(){
Node* lastNodePtr = tailPtr->getPrevNodePtr();
Node* prevNodePtr = 0;
char poppedData = '$'; //empty stack
if (lastNodePtr != 0){
prevNodePtr = lastNodePtr->getPrevNodePtr();
poppedData = lastNodePtr->getData();
}
else
return poppedData;
if (prevNodePtr != 0){
prevNodePtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(prevNodePtr);
}
else{
headPtr->setNextNodePtr(0);
tailPtr->setPrevNodePtr(0);
}
return poppedData;
}
char peek(){
Node* lastNodePtr = tailPtr->getPrevNodePtr();
if (lastNodePtr != 0)
return lastNodePtr->getData();
else
return '$'; // empty stack
}
};
int main(){
Stack stack;
string expression;
cout
cin >> expression;
int index = 0;
while (index
char symbol = expression[index];
if (symbol == '{' ){
stack.push(symbol);
index++;
continue;
}
else if (symbol == '}' ){
char topSymbol = stack.pop();
if (topSymbol == '{' && symbol == '}') {
index++;
continue;
}
else{
cout
return 0;
}
}
else{
cout
return 0;
}
}
if (!stack.isEmpty()){
cout
return 0;
}
cout
return 0;
}
Q4 - 20 pts) Consider the code given to you to determine whether an expression of parentheses is balanced or not using a Doubly Linked List implementation of a Stack. Modify the code (given in the main function) to determine the maximum depth of nested parentheses in a given expression, provided the expression is balanced. Note that your code should be also able to check whether a given expression of parentheses is balanced or not. If an expression is not balanced, you should not print the value for the maximum depth of nested parentheses: your program should just print the message that the expression is not balanced and terminate. For simplicity, you can assume that the only parenthesis symbols of use are { and }. The maximum depth of nested parentheses in a balanced expression is the largest number of open parentheses { in the stack at any time. For example, the maximum depth of nested parentheses in the expression { {}{{{}}{}}} is 4. Contents of the Stack after reading the corresponding symbol in the expression { { { { { { { { { Max. = 4 { { { { { { { { } } { { { { { {
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help