Thread: Need Delimiter Program helpful hints.

  1. #1
    Unregistered
    Guest

    Need Delimiter Program helpful hints.

    I am trying to write a C program that will determine whether a string of characters from the set "(, ), {, }, [, ]" is well formed; that is, if the scope delimiters come in matching pairs, and are properly nested. I need some helpful hints to approach writing this program.

    For example, this is a correctly formed string:

    {{()[]}}

    The input to the program is strings can be no more than 72 symbols from the above set of characters followed by a dollar sign '$'. (I can use '\n' to terminate the input string.) The input can be either from the terminal or from an input file; this is optional.

    For each input string, the program must either state that the string is well formed or indicate the character position from the left where there is a mismatch. Here is what the output will look like for these input strings:

    $ is OK.
    ()$ is OK.
    ()[]$ is OK.
    {{()[]}}$ is OK.
    ([)]$ is NOT OK (at symbol 3)
    ([$ is NOT OK (at symbol 3)
    ()][$ is NOT OK (at symbol 3)
    }$ is NOT OK (at symbol 1)

    The algorithm is as follows:

    Start with an empty stack.
    For each input character,
    if it is a left delimiter "{, (, ["
    push it on the stack.
    If it is a right delimiter "}, ), ]" it must the left
    delimiter on top of the stack:
    if the stack is empty,
    the string is bad already;
    if the stack isn't empty,
    pop and check the popped character
    and the input character for a match.
    If no mismatches occur before the end of the input string and the
    stack is empty when the '$' is encountered, the string is well formed.

    The algorithm needs to use the following stack operations :

    void Push(StackEntry item, Stack *s)
    void Pop(StackEntry *item, Stack *s)
    Boolean StackEmpty(Stack *s)
    Boolean StackFull(Stack *s) /* if needed */
    void CreateStack(Stack *s)

    These functions are provided in two other programs.

    Follow this structure EXACTLY:

    Implement the delimiter-checking algorithm as a function called DelimCheck which checks a string passed to it as a parameter.

    Write a main program that contains a loop which reads and echo prints one line of input, calls DelimCheck, and prints the results.

    The loop ends when there are no more input lines.
    The printing of the final results of the check cannot be inside DelimCheck. The printing must be done either in the main routine or in a function called by the main routine.
    Remember to comply with the firewall principle of using an abstract data type; that is, use the routines in your program in such a way that the application program does not access the stack in any way other than through the operations.


    Thanks.

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    £100 will see it will be ready for you 2moro

    I mean by god you have almost step by step instructions. Where are you stuck. You offer no code of your own to show that you have at least attempted the problem so if you can't be bothered to do it yourself and you also have a spare £100 then full commented source can be provided.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    >I am trying to write a C program....

    I think that

    "I am trying to let people write a C program for me...."

    is a better introduction of your posting.

  4. #4
    Unregistered
    Guest
    I am not asking for anybody to write my program. I am asking for helpful hints to approach writing the program. I guess that is a no-no. I will return after I write the program if I am having problems. Sorry for the bother.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    while( string[x] )
    {
        if( string[x] == opening character )
            push( string[x] )
        else
        if( string[x] == close character )
            if( a_match_pair( pop( ), string[x] ) == FALSE )
                return INVALID
        }
        else
            ignore character
        x++
    }
    return VALID
    You turn it into actual code.

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Unregistered
    Guest

    Smile

    Thanks Quzah. I appreciate the helpful hint without the prior posters flame throwing. That was all I was looking for.

  7. #7
    Unregistered
    Guest
    Can anybody provide some insight how I can get my program
    to work correctly per the instructions above? I am close. Thanks.


    #include <stdio.h>
    #include "stack.c"
    #define length 100

    void DelimCheck(void);
    void CheckPrint(void);
    void CheckPrint1(void);


    main()
    {
    while(!feof(stdin))
    {
    printf("Input Delimiter: ");
    DelimCheck();

    }
    }

    void DelimCheck(void)
    {
    StackEntry item;
    Stack stack;
    CreateStack(&stack);

    while (!StackFull (&stack) && (item=getchar()) != '\n' && (item=getchar(
    )) != '$' && !feof(stdin))
    {

    if (item == '{' )
    Push(item, &stack);

    if (item == '[' )
    Push(item, &stack);

    if (item == '(' )
    Push(item, &stack);

    if (item == '}' )
    { Pop(&item, &stack);
    if (item !='{')
    CheckPrint1();
    }
    if (item == ']')
    {
    Pop(&item, &stack);
    if (item !='[')
    CheckPrint1();
    }
    if (item ==')' )
    {
    Pop(&item, &stack);
    if (item !='(')
    CheckPrint1();
    }
    if (item == '\n' )
    {
    Pop(&item, &stack);
    if (item !='')
    CheckPrint1();
    }
    if (item == '$' )
    {
    Pop(&item, &stack);
    if (item !='')
    CheckPrint1();
    }


    }


    Pop(&item, &stack);
    if (item == '{' )
    CheckPrint1();

    if (item == '[' )
    CheckPrint1();

    if (item == '(' )
    CheckPrint1();

    if (item =='\n')
    CheckPrint();

    if (item =='$')
    CheckPrint();


    }

    void CheckPrint(void)
    {
    printf(" is OK. \n");
    exit(1);
    }


    void CheckPrint1(void)

    {
    printf(" is NOT OK. (at symbol )\n");
    exit(1);

    }









    Output:




    > cc -o delim delim.c
    > delim
    Input Delimiter: $
    Stack is empty
    > delim
    Input Delimiter: ()$
    Stack is empty
    > delim
    Input Delimiter: ()[]
    Stack is empty
    > delim
    Input Delimiter: ([)]$
    Stack is empty
    > delim
    Input Delimiter: }
    Stack is empty

  8. #8
    Registered User foniks munkee's Avatar
    Join Date
    Nov 2001
    Posts
    343
    Code:
    #include "stack.c"
    #include "stack.h" perhaps?

    Code:
    main()
    should be int main() and then you want to return 0 in your main function.

    Code:
    while(!feof(stdin)) 
    { 
    printf("Input Delimiter: "); 
    DelimCheck(); 
    }
    I wouldn't have thought the while(!feof(stdin)) construct would work very well - i.e. I just compiled this and she don't work.
    Last edited by foniks munkee; 02-16-2002 at 06:43 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  2. BOOKKEEPING PROGRAM, need help!
    By yabud in forum C Programming
    Replies: 3
    Last Post: 11-16-2006, 11:17 PM
  3. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM