CODEWITHSUNDEEP
javalinked-listcharstack
artemis
artemis

Reputation: 7251

Create a linked-list of characters on a stack?

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?

Upvotes: 1

Views: 5575

Answers (3)

artemis
artemis

Reputation: 7251

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");         
   }    
}  
}

Upvotes: 0

mikek3332002
mikek3332002

Reputation: 3562

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;
}

Upvotes: 1

Linda Cai
Linda Cai

Reputation: 66

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

Upvotes: 1

Related Questions