Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stack struct function

  1. Mar 7, 2015 #1
    Hello

    I am writing the balance function that should figure out whether the left and right parens ( ) , the left and right brackets [ ] , and the left and right curly brackets { } are properly matched and nested in the string arg. For instance,

    examples "(sldkj[slkdfjk{slkdfjsl(sldkjf(lkjsd)slkdfj)sldkfj}slkdjf]sldkfj)": balanced,
    "(((( [[[[ ]]]]{{{{ }}}} ))))": balanced
    "([)]": not balanced (even though we have left & right paren and a left & right bracket)
    "": balanced, no parens means no mismatch

    Code (Text):

      bool balanced(const string & line)
    {
       Stack sk;
       initialize(sk);
       if (line.size() > STACK_SIZE) die("stack overflow");
       for (unsigned i = 0; i < line.size(); i++)
       {
         switch (line[i])
         {
         case '(':
           push(sk, line);
           if (line[i] == ')')
           {
             if (top(sk)== "(") return 0;
             else  pop(sk);
           }
         case '[':
           push(sk, line);
           if (line[i] == ']')
           {
             if (top(sk) == "[") return 0;
             else  pop(sk);
           }    
         case'{':
           push(sk, line);
           if (line[i] == '}')
           {
             if (top(sk) == "{") return 0;
             else  pop(sk);
           }  
         default:
           ;
         }//switch
       }//for
       
       if (elements(sk) == 0) return 1;
       else return 0;
    }//balanced
     
     
  2. jcsd
  3. Mar 7, 2015 #2

    Mark44

    Staff: Mentor

    Do you have a question?
     
  4. Mar 7, 2015 #3
    ohh, yeah I am not getting what I a, suppose to get. I want to know my mistakes first time dealing with stack
     
  5. Mar 7, 2015 #4
    Without going into too much detail, you need to think about the stack as a record of what you've read so far. Add (push) opening brackets onto the stack when encountered, remove (pop) MATCHING closing brackets when encountered with no error, return error iff you encounter a closing bracket that does NOT match the opening bracket on top of the stack, and return success iff you get to the end of the string with the stack completely empty. Your code does not do this.
     
  6. Mar 7, 2015 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Did you test it with some test cases? Did it work?

    Can you explain what that part is supposed to do?

    For a code like "(a)", if you go through your code line by line, what happens and what is supposed to happen?
     
  7. Mar 7, 2015 #6
    No I didn't test it. Even if I had the inclination to, this site doesn't allow detailed answers to homework type questions. What this code is about is Push Down Automata. They are pretty simple, you've got a function that takes the current symbol in the line, and the symbol on top of the stack (or empty stack) as an input. In your case you've got 4 open closing brackets and end of line symbol, same for the stack with an empty stack symbol that makes 5*5 =25 possible inputs. All you need to do is draw up a 5*5 table and decide what needs to be done in each case, and put it in to code. If you use a switch statement with 25 possibilities based off this table, its ugly code but will work.
     
  8. Mar 8, 2015 #7
    well, I believe there's an error in the switch ( ---- )

    I am trying to check each single char of the given string and match it with the cases I have
    so let's say the first char was '(' it will be pushed to the stack, but having the following if statement seem useless
    that's why I posted my question here I want someone to start with me step by step or give me a push with pseudocode

    bool balanced(const string & line)
    {
    Stack sk;
    initialize(sk);
    if (line.size() > STACK_SIZE) die("stack overflow");
    for (unsigned i = 0; i < line.size(); i++)
    {
    if (line == '(') { push(sk, line); }
    if (line == ')')
    {
    if (top(sk) != "(") return 0;
    else { pop(sk); }
    }
    if (line == '[') { push(sk, line); }
    if (line == ']')
    {
    if (top(sk) != "[") return 0;
    else { pop(sk); }
    }
    if (line == '{') { push(sk, line); }
    if (line == '}')
    {
    if (top(sk) != "{") return 0;
    else { pop(sk); }
    }
    }//for
    if (elements(sk) == 0) return 1;
    else return 0;
    }//balanced
     
    Last edited: Mar 8, 2015
  9. Mar 8, 2015 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    @Fooality: I asked fadi_nzr, not you, sorry for the confusion.

    @fadi_nzr: That approach starts to look better now.
    You don't have to push every single letter on the stack (who cares about letters, for example?).
    You are comparing/pushing the whole line here? I would expect the whole logic to use single characters only.
     
  10. Mar 8, 2015 #9
    I know that I don't want to push the whole line, but instead just the char,
    take look at my push function it has a string argument not char.

    void push(Stack & stack, const string & item)
    {
    if (stack.elements == STACK_SIZE) die("Stack Underflow");
    stack.data[stack.elements++] = item;
    }//push
     
  11. Mar 8, 2015 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Then you'll need a string with a single char to call your function. Or overload it with the ability to push a char.

    (Is that supposed to read "underflow"?)
     
  12. Mar 8, 2015 #11
    I should say something like push(sk, line); // what I meant
    but since one of the push function argument is string I cannot say that
    so you mean I have to change
    void push(Stack & stack, const char& item)
     
    Last edited: Mar 8, 2015
  13. Mar 8, 2015 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    There are many ways to implement this, but no matter what exactly you do you should only put the single character onto the stack, not the full line. A function void push(Stack & stack, const char& item) looks like the easiest way.
     
  14. Mar 8, 2015 #13
    with this implementation worked for me/ what other ways I can do to push a single char instead of changing the string argument to const char

    bool balanced(const string & line)
    {
    Stack sk;
    initialize(sk);
    if (line.size() > STACK_SIZE) die("stack overflow");
    for (unsigned i = 0; i < line.size(); i++)
    {
    if (line == '(') { push(sk, line); }
    if (line == ')')
    {
    cout << top(sk) << endl;
    if (top(sk)!="(") return 0;
    else { pop(sk); }
    }
    if (line == '[') { push(sk, line); }
    if (line == ']')
    {
    cout << top(sk) << endl;
    if (top(sk) != "[") return 0;
    else { pop(sk); }
    }
    if (line == '{') { push(sk, line); }
    if (line == '}')
    {
    cout << top(sk) << endl;
    if (top(sk) != "{") return 0;
    else { pop(sk); }
    }
    }//for
    if (elements(sk) == 0) return 1;
    else return 0;
    }//balanced
     
  15. Mar 8, 2015 #14

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That implementation cannot work. Imagine line="a(". It is clearly unbalanced, but none of your if-statements should match so the for loop does nothing, your stack is empty and the result would be "matching".

    Depending on the language and the interpreter, line might get accepted as string, otherwise there is some char to string conversion function.
     
  16. Mar 8, 2015 #15
    I tried "a(" and it returned 0 !!
     
  17. Mar 8, 2015 #16

    Mark44

    Staff: Mentor

    That's what mfb is saying.
     
  18. Mar 8, 2015 #17
    Oh, sorry I'm new to this forum.
     
  19. Mar 9, 2015 #18
    how he said the result will be "matching".
     
  20. Mar 9, 2015 #19

    Mark44

    Staff: Mentor

    With an input string of "a(" your code returns an incorrect value of 0. That was mfb's point - that your code doesn't work correctly.
     
  21. Mar 9, 2015 #20

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I think 0 means "not matching". But then the code has another problem at this line:
    if (elements(sk) == 0) return 1;

    Which then means this test case should fail: "ab" - I guess it gives 0 as well, but it is matching and should give 1 (but for sure something different from "a(").

    Anyway, here are typical test cases:

    a(
    ab
    a)
    ()
    )(
    I would expect that they all give the same result with your code, but some of them are matching and some are not.
    (
    )
    Those two could be interesting as well.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Stack struct function
Loading...