Using Stacks and Queues (Arithmetic expression evaluate)

lilu_0608

[code]
Validate test and pseudocode.

I. validate test
  
At the first, a table and some principles for ADT will be defined.


Token        State sign
PLUS, MULT, DIV        a
Operand        b
LPAR        c
RPAR        d
MINUS        e


1.        The arithmetic expression must start with operand, MINUS, or LPAR (b, e, and c).
2.        The arithmetic expression must finish with operand, or RPAR (b and d).
3.        Every successive two tokens must satisfy:
ab, ac, ba, bd, cb, da, be, ce, de, eb, ec, cc, dd.(e.g. ce mean LPAR and MINUS can be successive, ‘ba’ mean a operand and PLUS can border upon).
4.  The number of LPARs and RPARs must be same, that mean the number of c and d must be same.
5.  If a LPAR appear, a RPAR must appear after (That mean, if c appears, d must be after c).
If the expression is not valid an InvalidExpressionException is thrown and the whole process is terminated.
Now, there are four examples will show how the validate test works.

There is an arithmetic expression ( (7 * ( 23 – 105 / 15 ) )- 19 )
That is,

(        (        7        *        (        23        -        105        /        15        )        )        -        19        )
Now from the 1st element transfer the token to state number, and put them into a queue called Q

c        c        b        a        c        b        e        b        a        b        d        d        e        b        d

From Q, we can know that,
1. This expression starts with operand (state number is b).
2. This expression finishes with operand (state number is b).
3. Every successive two tokens are satisfied (cc, cb, ba, ac, cb, be, eb, ba, ab, bd, dd, de, eb and bd).
4. These are three LPARs and three RPARs. In other word, there is three c and three d.
5. LPAR is in front of RPAR. In other word, c is in front of d.
So this is a valid arithmetic expression.
There is an arithmetic expression  – 9 * ( 23 – 105 / 15 ) - ( - 15 + 1 )
That is,
-        9        *        (        23        -        105        /        15        )        -        (        -        15        +        1        )

Now from the 1st element transfer the token to state number, and put them into a queue called Q

e        b        a        c        b        e        b        a        b        d        e        c        e        b        a        b        d

From Q, we can know that,
1.        This expression starts with MINUS (state number is e).
2.        This expression finishes with RPAR (state number is d).
3.        Every successive two tokens are satisfied (eb, ba, ac, cb, be, eb, ba, ab, bd, de, ec, ce, eb, ba, ab, and bd).
4.        There are two LPARs and Two RPARs.
5.        LPARs always have a RPAR after themselves.
So this arithmetic expression is valid.

There is an arithmetic expression 7 * ( 23 – 105 / 15- ) 19
That is,

7        *        (        23        -        105        /        15        -        )        19

Now from the 1st element transfer the token to state number, and put them into a queue called Q

b        a        c        b        e        b        a        b        e        d        b

From Q, we can know that,
1.        This expression starts with operand (state number is b).
2.        This expression finishes with operand (state number is b).
3.        ed and db are not satisfied.
So, this arithmetic expression is not valid.

These is an arithmetic expression 9 * 7 ) + ( 8 – 5) * ( 6
That is,

9        *        7        )        +        (        8        -        5        )        *        (        6
Now from the 1st element transfer the token to state number, and put them into a queue called Q

b        a        b        d        a        c        b        e        b        d        a        c        b

From Q, we can know that,
1.        This expression starts with operand (state sign is b).
2.        This expression finishes with operand (state sign is b).
3.        Every successive two tokens are satisfied (ba, ab, bd, da, ac, cb, be, eb, bd, da, ac, cb).
4.        There are two LPARs and two RPARs. (Two e and two d).
5.        There is not RPAR after the second LPAR.
So this arithmetic expression is not valid.

        After validation, the result is below:
                ( (7 * ( 23 – 105 / 15 ) )– 19) ………………………....Valid
                – 9 * ( 23 – 105 / 15 ) - ( - 15 + 1 ) ...............................Valid
                7 * ( 23 – 105 / 15- ) 19 .............................................Invalid
9 * 7 ) + ( 8 – 5) * ( 6 .................................................Invalid

II. Validate test pseudocode

Algorithm validate_start_element(EL):
        Input: a state sign from Q
        Output: boolean value that indicates whether the EL is valid
        if EL<>;b  or  EL<>;e  or  EL<>;c then
                throw an InvalidExpressionException

Algorithm validate_finish_element(EL):
        Input: a state sign from Q
        Output: boolean value that indicates whether the EL is valid
        if EL<>;b  or   EL<>;d then
                throw an InvalidExpressionException

Algorithm validate_successive_two_elements(EL1, EL2):
        Input: successive two state signs EL1 and EL2 from Q
        Output: boolean value that indicates whether the EL is valid
        EL

lilu_0608

有些表格无法正常显示，请见谅。