stack

[Justin Fox]

ok i have a program to do, that is supposed to take and expression from a user and calculate it, and tell what it equals, or if it is not a valid expression.

and by an expression i mean for example:

(1 + (3 * ( 5 - 4 )))

ok here is my question...

how do i get the scanner to scan each individual char/num.

do i take it as a string, and search it for char or numbers?

because in the program i have to put the numbers in one stack and the

operators in another.

but when or if i do have to do a loop to search the string

"( 1 + ( 3 * ( 5 - 4 )))"

can i convert the char that is actually a number, into an integer?

and after i do this and get all the nums, and ops in their stacks, the

algorithm says to pop the first two in the number stack and the first

operator in that stack, then solve that, then push that found value in the

number stack.

and can i do, for instance?

    
NumStack.push(NumStack.pop()OpStack.pop()NumStack.pop());

thanks,
Justin..

[Justin Fox]

and also, he wants the ^ to basically equal like, 3^2 = 9;

how do i do that if the user is entering a expression of their choice?

nevermind, i under stand, but how do i make ^ = to java's version of how to

raise a number to a certain power?

which is Math.pow(int,int);

could i do?

    
if(OpStack.pop() == '^');
(
   Math.pow(NumStack.pop(),NumStack.pop());
}

thx for replying...

Justin

[Justin Fox]

but wait, maybe i should do this first

 
   
int 1, 2;
 
//and do 
 
1 = NumStack.pop();
2 = NumStack.pop();
 
// and the solve it like so?
 
result = (2OpStack.pop()1);
 

because if i put the expression in a stack, its going to come out in reverse.

so i need to evaluate each small expression by reversing the .pop()'s.

thanks,

Justin

[Justin Fox]

here is some of my code....

and i know i could've switched, but i was lazy.

    
 

import java.util.Scanner;
 
public class Stackcrap 
{
int 1,2;
int Stack NumStack;
char Stack OpStack;
String Answer = "";
int [] array;
 
Scanner scan = new Scanner(System.in);
 
do{
System.out.println("Enter an expression: ");
Answer = scan.nextLine();
array = new int [Answer.length()];
 
for (int i = 0; i < array.length; i++)
{
array[i] = Answer.charAt(i);
}
 
for (int i = 0; i<array.length;i++)
{
if((int)array[i] == integer)
{
NumStack.push(array[i];
}
if(array[i] == '+' || array[i] == '-' || array[i] == '/' || array[i] == '*' || array[i] == '%' || array[i] == '^')
{
OpStack.push(array[i];
}
if (array[i] = ')')
{
//while loop to figure out the indicated operation.
}
}while(!Answer.equalsIgnoreCase("quit");

thanks for the replies...

Justin

[Justin Fox]

ok, my proffesor said we have to create our own stack driver class...

but doesn't java already have a predefined stack class with the following methods?

push();
pop();
isNotEmpty();
isNotFull();
peek();
dump();

these are already ready for you to use right?...then why make another

implementation of stack when it already exists...

oh and also, like say a user inputs the following at the prompt.

  
C:> 
 
Enter an Expression: (3 + (2 * (4 - 5)))
  

is there away where i can scan each individual character, switch the numerical values (0 - 9), and the operators(+,-,*,/,%,^).

and at the same time be loaded them into two different stacks??

oh! and i have another important question..

can i create my class as follows?
or is it legal, is a more reasonable question.

   
public class Stack
{
public Stack(Object intOrChar)
{
}
 
   }
 
 

because i want to create a stack class, but NOT! two different ones, one to hold a char, and one to hold a int.

and another thing, IF i wanted to compare a char to an int could i do the following?

    
for(int i = 0; i< array.length;i++)// where array is an array of chars
{                                  // loaded from a user input.
if((int)array[i] == Integer)
{
NumStack.push(array[i]
}

thanks,
Justin
[ June 06, 2006: Message edited by: Justin Fox ]

[Stan James]

Hi, I think we're tackling several problems at once and need to focus on one.

Yes, Java has a Stack class. See the JavaDoc and find Stack in the left class list to see the methods. It's up to your prof whether he wants you to use that one or make the problem a little harder and write your own.

If you have to write your own, try to write a MyStack that will make this code say "true". You can put this in the main() of a class called Tester or something.

MyStack stack = new MyStack();
System.out.println( stack.empty() );

Only after that works, make these work:

stack.push("one");
stack.push("two");
System.out.println( !stack.empty() );
System.out.println( 2 == stack.size() );

Then add these lines:

System.out.println( "two".equals( stack.pop() );
System.out.println( "one".equals( stack.pop() );
System.out.println( stack.empty() );

Note that this stack only works with Strings, so you'll have to use String types for parameters and return values. If you get that working we can talk about how to use ints and chars.

Sound fun?

[Justin Fox]

ok here is the stack driver, i can't seem to figure out how to define the pop() method

    
public class Stack
{
public int [] array;
public int top = -1;
public int count = 0;
public int size = 0;
 
public Stack(int number)
{
array = new int [number];
 

public void push(int Num)
{
 
if(array.isNotFull())
{
top++
array[top] = Num;
}
 
}
 
publc void pop()
{
//??
}
 
public boolean isNotFull()
{
if(Stack.size() != array.length)
return true;
else
return false;
}
 
public boolean isNotEmpty()
{
if(Stack.size <= 0)
return false;
else
return true;
)
 
public int Size()
{
for(int i = 0; i < array.length; i ++)
{
count++
}
size = count;
 
return count;
}
 
public int peek()
{
return array[i];
}
 
public String dump()
{
String result = "";
 
for (int i=0;i<array.length;i++)
{
result += (String)" array[i]";
}
 
return "Contents: " + result;
 
}
  }

thanks,
Justin

[Stan James]

That looks pretty close. An array-based stack is pretty fast and simple, but has a fixed size as you set it up in your constructor. It will do the job for a school assignment with reasonable limits. After this class, use the one in the JDK library.

You want pop() to return the most recently pushed value. What index do you have that points to the most recently pushed entry? What do you want to do to that index before you return? Think about calling push() three times then pop() three times. Draw the array and track the index on paper if that helps.

Your size() returns the capacity of the array. (And there is a much easier way to get that from an array.) Is that what you want? Or the number of entries currently in the stack? Which index will tell you that?

Your push() fails silently if the stack is full. Think about what it might do to indicate an error instead.

Does this compile? peek() is using an "i" that I don't see defined. I think you want that same index again here!

Translate the little set of tests I suggested into ints instead of strings and see how your stack class works. You'll have it in no time. Keep having fun!

[Justin Fox]

ok i modified the driver class, and implemented a main class....

but when i call dump, it calls it infinitely..

and i can't figure out why...

    
// Stack.java driver class
 
public class Stack
{
public int count = 0, size = 0, top = -1;
public String result;
public int [] array;
public enum errormsg{UNDERFLOW, OVERFLOW};
 
public Stack(int number)
{
array = new int [number];
}
 
public void push(int num)
{
if(isNotFull())
{
top++;
array[top] = num;
}
else
{
stackError(errormsg.OVERFLOW);
 
}
}
 
public int pop()
{
    if( isNotEmpty() )
        return array[top--];
    else
    {   stackError( errormsg.UNDERFLOW );  }
return 0;
  }
 
public int peek()
{
if(isNotEmpty())
return array[top];
else 
stackError(errormsg.UNDERFLOW);
return 0;
}
 
public boolean isNotFull()
{
return top<array.length-1;
}
 
public boolean isNotEmpty()
{
return top >= 0;
}
 
public void dump()
{
 
System.out.println("\t\t\t top: " + top + " Contents: " );
int front = top;
while(front>0)
System.out.println(array[top--] + " ");
}
 
public void stackError(errormsg msg)
{
 switch (msg)
{
case UNDERFLOW:
System.out.println("stack is empty!");
break;
case OVERFLOW:
System.out.println("stack is full!");
break;
}
}
}

and i have a main class too...

i dont understand why you return 0 in the pop and push function, why not just make the void and not return anything?.. all you want to do is take the value at top out and the make top point to top--, but how do you remove a value from a place in an array, i know you could say array[top] = 0;

but can you say array[top] = null;

or would it give a null pointer exception?

and in the dump method...

i have it print out

"top: Contents: "

but when i call dump all it does is print..

top: 0 contents:

over and over again..

but i didn't call the function recursivley ... and i said...oh wait..

i need to have i ++ lol in the while loop

im gay, ok thanks, but try and help me answer my other questions...

thx
Justin

oh and here is my main class..

    
// StackImple.java stack main class
 
import java.util.Scanner;
 

public class StackImple
{
public static void main (String[]args)
{
 
Scanner scan = new Scanner(System.in);
 
Stack NumStack, OpStack;
String answer;
char dop;
 
//______________________________________________________
 
System.out.println("Enter an Expression: ");
answer = scan.nextLine();
char [] charArray = new char [answer.length()];
NumStack = new Stack(answer.length());
OpStack = new Stack(answer.length());
 
NumStack.push(3);
NumStack.dump();
 
while(!answer.equalsIgnoreCase("x"))
{
for(int i = 0; i< answer.length(); i++)
{
charArray[i] = answer.charAt(i);
//System.out.println(charArray[i]); - debug
}

for(int i = 0; i<charArray.length; i++)
{

 
switch (charArray[i])
{
case 0:
NumStack.push(0);
break;
case 1:
NumStack.push(1);
break;
case 2:
NumStack.push(2);
break;
case 3:
NumStack.push(3);
break;
case 4:
NumStack.push(4);
break;
case 5:
NumStack.push(5);
break;
case 6:
NumStack.push(6);
break;
case 7:
NumStack.push(7);
break;
case 8:
NumStack.push(8);
break;
case 9:
NumStack.push(9);
break;
 

}
}
NumStack.dump();
}
 
}
}
 

[Justin Fox]

if i switch variable containing a char value,

do i need to do this?

switch(value)
{
case '0':
NumStack.push(0);
break;
}

??

thanks,
Justin

[Rusty Shackleford]

 public void dump()
{
 
System.out.println("\t\t\t top: " + top + " Contents: " );
int front = top;
while(front>0)
System.out.println(array[top--] + " ");
}
    

Why is this an infinite loop? Look at the exit condition. This loop is either going to run 0 times, or just keep running.

[Justin Fox]

is there anyway to convert a char to an int in java?

i tried

char value = charArray[i];
NumStack.push((int)value);

plz help me!!

[Rusty Shackleford]

int value = charArray[i];//no cast necessary because char is a subset of int
NumStack.push(value);

Why not just store them as chars? Or just immediately convert the input to an int?
[ June 08, 2006: Message edited by: Rusty Shackleford ]

[Justin Fox]

ok, i have the other crap taken care of...

but when it picks up the char '^' for example:

2^2 = 4, but the prof doesnt want us using math.pow, because its only

for exponets that are non integer...

i tried a recursive method, but im stuck...

here is my code so far

    
 
public static int recExp(int num1, int num2)
{
if (num2 == 1)
return num1;
 
if (num2 == 2)
return num1 * num1;
 
return recExp(?,num2-1);
}
 
i dont know how to keep the original num1 preserved so i can multiply by it each time recExp is called.
 
please help!
justin

[Rusty Shackleford]

If you want to pass a value recursively(or a non-recursive method call for that matter), then add it to the recursive call. It is just this simple:

return recExp(num1,num2-1);

If you change the value somewhere in the method, then of course num1 will not be its original value, but you should have an idea how to do it in that case. Since you never modify num1, this is not an issue in this case.