Create a linked-list of characters on a stack?

Question

I have an assignment that I'm struggling with.

Write code based on referenced-based stack to implement the balance check of a user input string with ‘{’, ‘}’, ‘(’, ‘)’, and ‘[’, and ‘]’. For instance, if user inputs “(abc[d]e{f})”, your code should say that the expression is balanced.

I have the functions push / pop already written:

public void push(Object newItem) {
    top = new Node(newItem, top);
}  // end push

public Object pop(){
    if (!isEmpty()) {
        Node temp = top;
        top = top.getNext();
        return temp.getItem();
    } else {
        System.out.print("StackError on " +
                "pop: stack empty");
        return null;
    } // end if
} // end pop

However, what I am struggling with is understanding how to create a new node for each character. Could somebody please help me?

The idea here isn't to do with lists, it's about what conditions call for putting a character on or off the stack. — Rogue, Nov 01 '16 at 23:32
I didn't post the full assignment. The professors instructions are to be able to implement this with ARRAY based, and then LIST based. — artemis, Nov 01 '16 at 23:36
Write code to implement the following functions with an array-based stack: a. Ask for user input for any string of letters b. Within the string, if the number of ‘A’ is twice the number of ‘B’, output “Yes”, otherwise output “No.” 2. Write code based on referenced-based stack to implement the balance check of a user input string with ‘{’, ‘}’, ‘(’, ‘)’, and ‘[’, and ‘]’. For instance, if user inputs “(abc[d]e{f})”, your code should say that the expression is balanced. — artemis, Nov 01 '16 at 23:36
I don't think you need to create a "node" ... you can have either an array or a List of `char` (primitive) or `Character` (object) so your push/pop would be `public void push(Character c)` and `public Character pop()` — Stephen P, Nov 02 '16 at 00:28
Oh. or - Are you saying you can't use Java's `java.util.List` -- that you have to implement the data structure yourself from scratch? — Stephen P, Nov 02 '16 at 00:33
Hi, Stephen. That is correct. I have to implement it myself. I also can not use arrays AT ALL, so I can't make a character array. — artemis, Nov 02 '16 at 01:19

score 1 · Answer 1 · edited May 23 '17 at 12:24

The isbalanced mechanism simplified for [,],(,):

Always add(push) a [, or (
When you get to a ) check the last added character was a (. If it was remove(pop) it, otherwise mark as unbalanced.
When you get to a ] check the last added character was a [. If it was remove(pop) it, otherwise mark as unbalanced.
If the stack is empty by the end of the string, it is balanced.

In reponse to your comment

Based off an answer for iterate through the characters of a string

unbalanced=false;
for (int i = 0; i < s.length(); i++)
{
    char c = s.charAt(i);        
    if(c.equal('[')
    {
        push(c);
    }
    if(c.equal(']')
    { 
        Char tmp = (Char)pop();
        if(!tmp.equals('['))
            unbalanced=true;
            break;
        }
     }

}
if(pop()!=null)
{
   unbalanced=true;
}

This is what would work and I understand this conceptually. However, my issue is taking the characters and creating nodes out of them. — artemis, Nov 02 '16 at 01:19

Linda Cai · Answer 2 · 2016-11-02T00:55:17.007

1

Since your assignment instructions ask you to "Write code based on referenced-based stack", it seems your question is more about how to convert each of user's input string into a node. In that case, you can convert them first to a list of chars simply like this:

public class Main {
    public static void main(String[] args){
        String str = new String("[(a)bcde]");
        System.out.println(str.toCharArray());
    }
}

And then use ASCII table to tell whether it's a special character. eg: in above code:

(int) str.toCharArray()[0]  // will show ASCII code of '[', 91

Some useful implementations about Reference-based Stack

edited Nov 02 '16 at 00:55

answered Nov 02 '16 at 00:42

Linda Cai

66
2
6

I assume that case "(a[bc)de]" is not considered as balanced? otherwise there would be more conditions to consider – Linda Cai Nov 02 '16 at 00:50
Hi, thanks a lot for your answer! Unfortunately, I can't use this ebcasue I am NOT ALLOWED to use an array at all. Would you happen to have any further suggestions? – artemis Nov 02 '16 at 01:20
Or use substring. String str = "hello"; str.substring(0,1) -> 'h' – Linda Cai Nov 02 '16 at 04:39

score 0 · Accepted Answer · edited Jan 17 '17 at 00:48

Here is what the professor was looking for:

... }      
if(currChar.equals("["))
{          
 myStackRef.push("[");         
}         
if(currChar.equals("}") && myStackRef.peek().equals("{"))
{            
 myStackRef.pop();           
}       
if(currChar.equals(")") && myStackRef.peek().equals("("))
{         
 myStackRef.pop();      
}            
if(currChar.equals("]") && myStackRef.peek().equals("["))
{
  myStackRef.pop();         
}       
}       

if(myStackRef.isEmpty())
{
  System.out.println("Balanced"); 
}
else
{  
  System.out.println("Unbalanced");         
   }    
}  
}

Create a linked-list of characters on a stack?

3 Answers3

In reponse to your comment