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 � EL1 + EL2
if EL<>;ab or EL<>;ac or EL<>;ba or EL<>;bd or EL<>;cb or EL<>;da or EL<>;be or EL<>;ce or EL<>;de or EL<>;eb or EL<>;ec or EL<>;cc or EL<>;dd then
throw an InvalideExpressionException
Algorithm validate_place_LPAR_RPAR( ):
Input: a state s and an integer r
Output: boolean value that indicates whether the expression is valid
if !PAR.stack_isEmpty( ) then
throw an InvalidExpressionException
Algorithm element_transfer_state_sign(EL):
Input: an element EL of the expression
Output: a state sign
if EL = ‘*’ or EL = ‘+’ or EL = ‘/’ then
return ‘a’
else if EL = ‘(’ then
return ‘c’
else if EL = ‘)’ then
return ‘d’
else if EL = ‘-’ then
return ‘e’
else return ‘b’
Algorithm enqueue(o):
Input: an object o insert queue
Output: None
if queue_size( ) = N-1 then
throw a QueueFullException
Q[r] � o
r � (r+1) mod N
Algorithm dequeue( ):
Input: None
Output: Object from queue
if queue_isEmpty( ) then
throw a QueueemptyException
temp � Q[f]
Q[f] � null
f � (f+1) mod N
return temp
Algorithm queue_isEmpty( ):
Input: None
Output: Boolean
return(f = r)
Algorithm queue_size( ):
Input: None
Output: Integer
return (N – f + r) mod N
Algorithm NumberOfElements(ep):
Input: an expression
Output: a integer of the number of elements
return ep.length
Algorithm: stack_clear( )
Input: none
Output: none
while (! stack_isEmpty( )) do
pop ( )
Algorithm: queue_clear( )
Input: none
Output: none
while (! queue_isEmpty( )) do
dequeue( )
Algorithm: stack_isEmpty( )
Input: none
Output: boolean
return (t<0)
Algorithm: push(o)
Input: Object
Output: None
if stack_size( )=N then
throw a StackFullException
t � t + 1
S[t] � o
Algorithm: pop( )
Input: None
Output: Obejct
if stack_isEmpty( ) then
throw a StackEmptyException
return S[t]
Algorithm validate_test(expression &EP): // Arithmetic expression validate test
Input: an expression EP
Output: boolean value that indicates whether the expression is valid
element EL //EL is an element of expression
int n � NumberOfElements(EP) // n is the number of elements
queue Q // A queue store state sign
stack PAR // A stack that use to validate LPAR and RPAR
char S, T � null // S and T are state signs
Q.queue_clear( ) // clear queue Q
PAR.queue_clear ( ) // clear stack PAR
int r � 0 // state of method valid_place_LPAR_RPAR( ) just two states 1 or 0
for i � 0 to n-1 do
EL � EP.getElement(i) // get out the element of No.i
S � element_transfer_state_sign(EL) // transfer the EL to state sign
Q.enqueue (S)
S � null
for i � 1 to n do // start validate test
if i = 1 then
S � Q.dequeue( )
validate_start_element(S)
if S = c then
PAR.push(c)
if i >; 1 and i < n then
T � Q.dequeue( )
validate_successive_two_elements(S, T)
if T = c then
PAR.push(c)
if T = d then
PAR.pop( )
S � T
if i = n then
T � Q.dequeue( )
validate_successive_two_elements(S, T)
validate_finish_element(T)
if T = c then
PAR.push(c)
if T = d then
PAR.pop( )
validate_place_LPAR_RPAR()
return (valid expression)
Infix2postfix test and pseudocode
I. Infix2postfix test
The rules of infix transfer to postfix:
1. ‘#’ mean minus, this is a operator, it just need one operand, if a expression is #5, this mean #5 = -5
e.g. some expression like 7*(-5+6)/(-7), it should be transferred to 7*(#5+6)/(#7)
2. Take the tokens from left to right.
3. If the input token be for an operand, it is enqueued to the output buffer q3.
4. If the input token be for a LPAR, it is pushed onto the stack.
5. If the input token be for a RPAR, tokens are popped from the stack and enqueued to the output until the first LPAR token be popped. The popped LPAR token and the input RPAR token are both discarded.
6. If the input token be for an operator the action depends upon its precedence relative to that on top of the stack.
l If the precedence of the input token is greater than the of the token on top of the stack – of if the stack be empty of if the top be a LPAR token – the input token is pushed onto the stack.
l Otherwise the stack is popped and the popped token is enqueued to the output and then the input token is pushed onto the stack.
7. At end of input tokens are popped from the stack and enqueued to the output until the stack become empty.
8. The RPAR never be pushed onto stack.
The operator Precedence:
The operators MULT and DIV (usually coded as * and / ) have higher precedence than those for PLUS and MINUS (usually coded as + and - ).
Token In-Stack Precedence (ISP) In-Coming Precedence (ICP)
( -1 6
) 0 0
+ 2 2
- 2 2
* 3 3
/ 3 3
# (-) 4 5
operand 0 0
Figure: The precedence of tokens
Figure: Infix transfer to postfix flow chart
Infix2postfix test data
It will give out 2 examples for infix transfer to postfix.
A. 7 * (#5 + 6) / (#7)
Step Token Postfix Stack
1 7 7
2 * 7 *
3 ( 7 *, (
4 # 7 *, (, #
5 5 7 5 *, (, #
6 + 7 5 # *, (, +
7 6 7 5 # 6 *, (, +
8 ) 7 5 # 6 + *
9 / 7 5 # 6 + * /
10 ( 7 5 # 6 + * /, (
11 # 7 5 # 6 + * /, (, #
12 7 7 5 # 6 + * 7 /, (, #
13 ) 7 5 # 6 + * 7 # /
So, the postfix expression is 7 5 # 6 + * 7 # /
B. ( 3 * 3 – 4 * 5 * 8 ) / ( 2 * 6 )
Step Token Postfix Stack
1 ( (
2 3 3 (
3 * 3 (, *
4 3 3 3 (, *
5 - 3 3 * (, -
6 4 3 3 * 4 (, -
7 * 3 3 * 4 (, -, *
8 5 3 3 * 4 5 (, -, *
9 * 3 3 * 4 5 * (, -, *
10 8 3 3 * 4 5 * 8 (, -, *
11 ) 3 3 * 4 5 * 8 * -
12 / 3 3 * 4 5 * 8 * - /
13 ( 3 3 * 4 5 * 8 * - /, (
14 2 3 3 * 4 5 * 8 * - 2 /, (
15 * 3 3 * 4 5 * 8 * - 2 /, (, *
16 6 3 3 * 4 5 * 8 * - 2 6 /, (, *
17 ) 3 3 * 4 5 * 8 * - 2 6 * /
So, the postfix expression is 3 3 * 4 5 * 8 * - 2 6 * /
II. Infix2postfix pseudocode
Algorithm: dequeue( )
Input: None
Output: Object
if queue_isEmpty( ) then
throw a QueueEmptyException
return Q[f]
Algorithm: queue_size( )
Input: None
Output: Integer
return (N-f+r) mod N
Algorithm: push(o)
Input: Object
Output: None
if stack_size( )=N then
throw a StackFullException
t � t + 1
S[t] � o
Algorithm: pop( )
Input: None
Output: Obejct
if stack_isEmpty( ) then
throw a StackEmptyException
return S[t]
Algorithm: stack_isEmpty( )
Input: none
Output: boolean
return (t<0)
Algorithm: enqueued (o)
Input: Object
Output: None
if queue_size( ) = N – 1 then
throw a QueueFullException
Q[r] � o
r � (r+1) mod N
Algorithm: stack_size( )
Input: None
Output: integer
return t+1
Algorithm: stack_clear( )
Input: none
Output: none
while(! stack_isEmpty( )) do
pop ( )
Algorithm: queue_clear( )
Input: none
Output: none
while(! queue_isEmpty( )) do
dequeue( )
Algorithm: isOperand(o)
Input: an object
Output: Boolean
return ( o <>; ‘+’ or o <>; ‘-’ or o <>; ‘*’ or o <>; ‘/’ or o <>; ‘(’ or o <>; ‘)’ or o<>; ‘#’)
Algorithm: isRPAR(o)
Input: an object
Output: Boolean
return ( o = ‘)’ )
Algorithm: isLPAR(o)
Input: an object
Output: Boolean
return ( o = ‘(’ )
Algorithm: top( )
Input: none
Output: object
if stack_isEmpty then
throw a StackEmptyException
else
return Q[t]
Algorithm: ISP(o)
Input: object
Output: integer
if o = ‘(’ then
return -1
if o = ‘)’ then
return 0
if o = ‘+’ or o = ‘-’ then
return 2
if o = ‘*’ or o = ‘/’ then
return 3
if o = ‘#’ then
return 4
Algorithm: ICP(o)
Input: object
Output: integer
if o = ‘(’ then
return 6
if o = ‘)’ then
return 0
if o = ‘+’ or o = ‘-’ then
return 2
if o = ‘*’ or o = ‘/’ then
return 3
if o = ‘#’ then
return 5
Algorithm: infix_transfer (Q1)
Input: one queue
Output: Q2
A � Q1.dequeue( )
if Q1 = ‘-’ then
Q2.enqueue(‘#’)
else
Q2.enqueue(A)
while (!Q1.queue_isEmpty( )) do
B � Q1.dequeue( )
if A+B <>; ‘LPAR’ + ‘-’ then
Q2.enqueue(B)
else
Q2.enqueue(‘#’)
A � B
return Q2
Algorithm: infix2postfix (infix &INfix)
Input: an infix expression INfix, INfix is a queue.
Output: a postfix expression PO, PO is a queue
element EL
stack ST
queue PO
queue IN
int n � INfix.queue_size( )
ST.stack_clear( )
PO.queue_clear( )
IN � infix_transfer (INfix)
for i � 1 to n do
EL � IN.dequeue( )
if isOperand(EL) then // if EL is a operand
PO. enqueue(EL) // put EL into queue PO
continue
if ST.stack_isEmpty( ) then // if ST is empty
ST.push(EL) // push the EL onto stack ST
continue
if isRPAR(EL) then
while (!(ST.stack_isEmpty( ) or isLPAR(ST.top( ))) do
EL = ST.pop( )
PO.enqueue(EL) // take out operator from ST and enqueued PO before LPAR
ST.pop( ) // pop LPAR and discard
continue
if ISP(ST.top( )) < ICP(EL) then
ST.push(EL)
else
while (!(ST.stack_isEmpty( ) or ISP(ST.top( )) < ICP(EL))) do
PO.enqueue(ST.pop( ))
ST.push(EL)
while (!ST.stack_isEmpty()) do
PO.enqueue(ST.pop( ))
return PO
Evaluate test and pseudocode
I. Evaluate test
u If the token is for a number, the number is pushed onto the stack.
u If the token is for an operator which needs two operands, the top two numbers are popped from the stack, the operation is performed upon those two numbers and the result pushed back onto the stack.
u If the token is for an operator which needs just one operand, the top number are popped from the stack, the operation is performed with this number and the result pushed back onto the stack.
It will give out 2 examples for evaluating test, ‘4 4 * 9 4 * 6 * - 2 1 * /’ and ‘7 5 # 6 + * 7 # /’
A. 4 3 * 9 4 * 6 / - 2 1 * /
Token Operand 1 Operand 2 Value Stack
4 4
3 4, 3
* 4 3 12 12
9 4 3 12 12, 9
4 4 3 12 12, 9, 4
* 9 4 36 12, 36
6 9 4 36 12, 36, 6
/ 36 6 6 12, 6
- 12 6 6 6
2 12 6 6 6, 2
1 12 6 6 6, 2, 1
* 2 1 2 6, 2
/ 6 2 3 3
So, the result is 3.
B. 7 5 # 6 + * 7 # /
Token Operand 1 Operand 2 Value Stack
7 7
5 7, 5
# 5 -5 7, -5
6 5 -5 7, -5, 6
+ -5 6 1 7, 1
* 7 1 7 7
7 7 1 7 7, 7
# 7 1 -7 7, -7
/ 7 -7 -1 -1
So, the result is -1.
II. Evaluate pseudocode
Algorithm: dequeue( )
Input: None
Output: Object
if isEmpty( ) then
throw a QueueEmptyException
return Q[f]
Algorithm: queue_size( )
Input: None
Output: Integer
return (N-f+r) mod N
Algorithm: stack_size( )
Input: None
Output: integer
return t+1
Algorithm: push(o)
Input: Object
Output: None
if stack_size( )=N then
throw a StackFullException
t � t + 1
S[t] � o
Algorithm: pop( )
Input: None
Output: Object
if stack_isEmpty( ) then
throw a StackEmptyException
return S[t]
Algorithm: queue_isEmpty( )
Input: none
Output: boolean
return(f=r)
Algorithm: stack_isEmpty( )
Input: none
Output: boolean
return (t<0)
Algorithm: stack_clear( )
Input: none
Output: none
while(! stack_isEmpty( )) do
pop ( )
Algorithm: calculate(EL, y, x)
Input: EL is an operator, y and x are operand
Output: return value of y EL x
if EL = ‘+’ then
return y+x
if EL = ‘-’ then
return y-x
if EL = ‘*’ then
return y*x
if EL = ‘/’ then
return y/x
if EL = ‘#’ then
return 0 - y
Algorithm evaluate (postfix &PO)
Input: a postfix expression PO, PO is a queue.
Output: a result of expression PO
element EL
double x, y, r � 0
stack ST
int n � PO.queue_size( )
ST.stack_clear( )
for i � 1 to n do
EL = PO.dequeue( )
if EL<>; ‘+’ or EL<>; ‘-’ or EL<>; ‘*’ or EL<>; ‘/’ or EL<>;‘#’ then
ST.push(EL)
else
if EL = ‘#’ then
x � ST.pop( )
y � 0
r � calculate (EL, y, x)
ST.push(r)
else
x � ST.pop( )
y � ST.pop( )
r � calculate(EL, y, x)
ST.push(r)
if PO.queue_isEmpty( ) then
return ST.pop( )
else
return 0
lilu_0608 回复于：2004-12-14 06:47:14
有些表格无法正常显示，请见谅。
|
