Stacks

[xcarbonx]

Hi..i'm having some trouble coming up with the an algorithm for a problem im working on.

I am trying to check an arithmetic infix expression like:

(((6+2)/2)*(3-1)); //This is my input file(; marks end of line.)

I have to check to see if the statement is ok, or not ok, and if it has either a stack overflow or underflow. For example output would look like:

(((6+2)/2)*(3-1)) is Fine.

OR

(((6+2)/2)*(3-1) is not fine.

OR

((((((((6+2/2)*(3-1)) Stack Overflow!

My algorithm as of now is:

Open Files
Check to see if files ok
Read 1 char
While (inFile) AND char != ';'
if char == '(' AND stack !isfull()
push(char)
else if char == ')' AND stack !isempty()
pop (char)
else
ignore all other characters.
}

I'm having trouble understanding where and how to output the whole expression and if it is a stack underflow, overflow, or is ok. Also, how do you ignore all other characters (numbers, operators, etc).

[Momerath]

What defines "fine" as it's not matched parens (first example has 4 open and 3 close).

As for skipping number, operators, just don't include the last else as you don't need to do anything with them.

[xcarbonx]

sorry about that i typed it wrong. It is fixed.

[L7Sqr]

If the only thing you are worried about is that the number of parenthesis are balanced then you dont need a stack - although if you decide to transform the equation (to RPN, for instance) or evaluate it you will.

To ensure balance the following algorithm will work:

// pseudocode
while read token:
   if token == '(':
      increment left
   if token == ')':
      increment right
if left == right:
   equation is balanced
otherwise:
   unbalanced