Write a program that uses an array-based stack to determine if the number of cur

Question

Write a program that uses an array-based stack to determine if the number of curly-brackets are matched (i.e. does the number of '{' match the number of '}' ?). You must do this line by line. P.S. This reminds me of the story about "Polly Nomial"... "Once upon a time (1/T) pretty little Polly Nomial was strolling across a field of vectors when she came to the edge of a singularly large matrix. Now Polly was convergent and her mother had made it an absolute condition that she must never enter such an array without her brackets on." For the rest of the story, see: http://undcemcs01.und.edu/~ronald.marsh/LINKS/PERSONAL/math-tale.txt You can use a simple array as your stack (you must have a stack). You can statically declare the stack to be of size 100. You must have a PUSH routine and a POP routine. The PUSH and POP routines must get the stack passed to them and must return the modified stack to the main routine. The algorithm is as follows: 1. Clear the stack (why?) 2. Open the data file (a C program) 3. Scan the data file A. If you find a { push the stack B. If you find a } pop the stack C. If you find a new line character " " a. Increment your line counter b. Test the stack for left over { or } and print error message if there are 4. If EOF, print appropriate message. Your program MUST generate output as shown below. Sample output: -------------- There are too many { in line 116 There are too many } in line 130. End of file. Extra Credit: ------------- Split your program into 6 files (3 .c files and 3 .h files) and create a Makefile to compile the 3 files seperately and link them. Your Makefile file must have an 'all' option with targets for the 3 .c files. Your Makefile file must have options for the above listed targets. Your Makefile file must have a 'clean' option. Your Makefile file must at least have at variables for the compiler (CC) and the include path. If doing the extra credit, you MUST submit your files as a single tarball.

Explanation / Answer

The question has a lot of parts which I think ideally should be different questions.

However, I'm gonna answer the most important part of the question.

THE BALANCED PARENTHESIS PROBLEM:

Below is an implementation of the above stated problem that I wrote some time back.

/*Submitted By:- Waqas Hamid*/

#include<bits/stdc++.h>
#define LL long long int
#define s(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define ss(a) scanf("%s",a)
#define w(t) while(t--)
#define f(i,n) for(i=0;i<n;i++)
#define fd(i,n) for(i=n-1;i>=0;i--)
#define p(a) printf("%d",a)
#define pl(a) printf("%lld",a)
#define ps(a) printf("%s",a)
#define pc(a) printf("%c",a)
#define ent printf(" ")
#define mod 1000000007
#define PI 3.14159265
#define gs getline(cin,s)
#define pb push_back
#define mp make_pair

using namespace std;

stack<LL> st;

int main()
{
   string s;
   cin>>s;
   LL len=s.length(),i;
   for(i=0;i<len;i++)
   {
       if(s[i]=='('||s[i]=='{'||s[i]=='[')
       st.push(s[i]);
       else
       {
           switch(s[i])
           {
               case ')': if(st.top()!='(') {cout<<"Invalid Expression "; return 0;} st.pop(); break;
               case '}': if(st.top()!='{') {cout<<"Invalid Expression "; return 0;} st.pop(); break;
               case ']': if(st.top()!='[') {cout<<"Invalid Expression "; return 0;} st.pop(); break;
           }
       }
   }
   if(st.empty())
   cout<<"Valid Expression ";
   else
   cout<<"Invalid Expression ";
}

You can read a file into this and provide the inputs to the above program to solve your problems.

Hope this helps :)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.