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).

Edited 5 Years Ago by xcarbonx: n/a

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.

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
This article has been dead for over six months. Start a new discussion instead.