Can someone finish the program? I need to use Doubly Linked List. I need a C++ p
ID: 3915870 • Letter: C
Question
Can someone finish the program? I need to use Doubly Linked List. I need a C++ program that checks to see if parentheses (or brackets) in
expressions are valid or not. The program takes as input a text file that has a series
of expressions, one per line. An example input file could be:
[ ][ ][ ][ ]
( )
( try )
]
ok
{
((())) [][][]
[ ] [ ]
55 5 4 3 2 2 { ( [ (3 * 4 ) ] ( 8 + 1 ) ) }
)()(
hello
last
The program should read them in and determine if the brackets are arranged in a
valid way or not. The output should be a summary of the data file with the following
lines:
Statistics:
12 total lines.
8 valid lines.
4 invalid lines.
67% valid.
33% invalid.
As you can see from the example, a line is valid if it has no brackets, if it has brackets
of any kind, they must be nested properly, beginning with an open bracket ( or [ or {
and ending with a closed bracket } or ] or ) respectively. It is not enough to simply
count brackets as the following line is not valid:
( [ ) ]
despite it having the correct number of brackets, and the openings occurring before
the closings.
Here is my Code:
#include "l_char_stack.h"
using namespace std;
int main()
{
l_char_stack stack;
return 0;
}
-----------------------------
#include "l_char_stack.h"
l_char_stack::l_char_stack()
{
}
l_char_stack::l_char_stack(int mSize)
{
}
l_char_stack::~l_char_stack()
{
}
void l_char_stack::push(listObjType newItem)
{
}
listObjType l_char_stack::pop()
{
listObjType a;
a = listObjType();
return a;
}
listObjType l_char_stack::peek()
{
listObjType a;
a = listObjType();
return a;
}
bool l_char_stack::isEmpty()
{
return false;
}
bool l_char_stack::isFull()
{
return false;
}
void l_char_stack::clear()
{
}
int l_char_stack::depth()
{
return 0;
}
-------- l_char_stack.h --------
#include "char_linked_list.h"
class l_char_stack
{
private:
public:
l_char_stack();
l_char_stack(int mSize);
~l_char_stack();
void push(listObjType newItem);
listObjType pop();
listObjType peek();
bool isEmpty();
bool isFull();
void clear();
int depth();
};
----------- text input file---------------
()
[]
[[[]]]
a
b
c
d
e
)()()()(
(())(())(a)
Explanation / Answer
main.cpp
/* Contains main function. Driver program */
#include<iostream>
#include<fstream>
#include<string.h>
#include "stack.h"
using namespace std;
int main()
{
char str[MAX];
int no_of_lines = 0, valid_lines = 0;
ifstream f;
f.open("expression.txt");
if(f == NULL)
{
cout<<"Cannot open file!";
}
else
{
while(f)
{
f.getline(str, MAX);
if(f)
{
charStack s;
s.copyString(str);
if(s.validityCheck())
{
valid_lines++;
}
no_of_lines++;
}
}
}
cout<<"Statistics: ";
cout<<no_of_lines<<" total lines ";
cout<<valid_lines<<" valid lines ";
cout<<(no_of_lines - valid_lines)<<" invalid lines ";
cout<<(valid_lines*100)/no_of_lines<<"% valid ";
cout<<100-((valid_lines*100)/no_of_lines)<<"% invalid";
f.close();
return 0;
}
/* stack.h */
#define MAX 100
class charStack
{
int top;
char stack[MAX],str[MAX];
public:
charStack();
void copyString(char str2[]);
void PUSH(char c);
char POP();
int validityCheck();
};
/* validity.cpp */
#include<iostream>
#include<string.h>
#include "stack.h"
using namespace std;
charStack::charStack()
{
top = -1;
}
void charStack::copyString(char str2[])
{
strcpy(str,str2);
}
//Function to push into the stack
void charStack::PUSH(char c)
{
if(top == MAX - 1)
cout<<"Stack Overflow";
else
{
top++;
stack[top] = c;
}
}
//Function to pop from the stack
char charStack::POP()
{
if(top == -1)
cout<<"Stack Underflow";
else
return (stack[top--]);
}
int charStack::validityCheck()
{
int flag = 1;
char temp;
for(int i = 0; i < strlen(str); i++)
{
if(str[i] == '(' || str[i] == '[' || str[i] == '{')
{
PUSH(str[i]);
}
if(str[i] == ')' || str[i] == ']' || str[i] == '}')
{
if(top == -1)
{
flag = 0;
break;
}
else
{
temp = POP();
if(temp == '(' && (str[i] == '[' || str[i] == '{'))
flag = 0;
if(temp == '{' && (str[i] == '[' || str[i] == '('))
flag = 0;
if(temp == '[' && (str[i] == '(' || str[i] == '{'))
flag = 0;
}
}
}
if(flag && top == -1)
return 1;
else
return 0;
}