Re: How to evaluate an expression using Queue?

From: Michael Wojcik (mwojcik_at_newsguy.com)
Date: 03/16/04 

Date: 16 Mar 2004 02:23:10 GMT

In article <cede900a.0403140349.6b02f3b9@posting.google.com>, Shekhar_D_S@yahoo.com (Shekhar Somani) writes:
>
> "Write a Program in 'C' language to evaluate an expression using a
> Queue. You should not use the concept of Stack any where in your
> program."
>
> I know how to evaluate postfix expression using stack and infix
> expression using recursion, but I need to use Queue structure.
>
> I can not use techniques like Dequeue the Queue until end to reach the
> last element, or using a Double-Ended Queue (both to acquire LIFO
> indirectly from Queue structure). Note the words "the concept of
> stack", anything like stack cannot be used.

I'm not sure I would consider simulating LIFO removal using multiple
queues "stack-like", but fair enough.

Off the top of my head, I think you can construct an iterative
expression evaluator using two queues and some temporary variables.
The expression has to be infix[*], with parentheses to indicate
order of operation. I'll assume this is a four-function calculator,
so the queue elements are taken from the set

   {number, +, -, *, /, (, )}

(and optionally another symbol for end of queue, if the queue
doesn't provide an "isempty" predicate).

Note that all the operators are binary. That means a "simple
expression" is a tuple {number, operator, number}. Here's a
complete grammar:

value ::= number (one or more digits)
op ::= + | - | * | /
expression ::= value | expression op expression | (expression)

but some of these can be evaluated immediately, and some require
further processing. In particular, any "value op value" can be
replace with the result of the operation, and any "(value)" can
be replaced with value (ie remove parentheses that just surround
a number).

That gives you two reduction rules. The algorithm is to iterate
over the expression, reducing subexpressions that fit the rules,
until the expression is a single value. Use a three-element
sliding window, implemented with three temporary variables.

To iterate over the expression, use two queues, A and B, and three
temporary variables L, M, and R (for left, middle, and right):

1. Load the initial expression into queue A, by enqueuing each
element in turn, left-to-right.

2. If A contains only a single element that's a value, you're
done; dequeue and return it. Otherwise, if A contains fewer
than three elements, you have a malformed expression; return an
error.

3. Dequeue three elements from A into L, M, and R.

4. Reduction rule 1: If L is a value, M is an op, and R is a value,
   calculate the result and enqueue it in B, then go to 7.

5. Reduction rule 2: If L is "(", M is a value, and R is ")",
   enqueue M in B, then go to 7.
   
6. Nothing was reduced. Shift the window:

   6.1. Enqueue L in B.
   6.2. Assign M to L and R to M.
   6.3. Try to dequeue from A into R. If A is empty:
           6.3.1. Enqueue L and M in B.
           6.3.2. Go to 8.
   6.4. Go to 4.

7. A reduction happened. Reload L, M, and R:
   7.1. Try to dequeue from A into L. If A is empty, go to 8.
   7.2. Try to dequeue from A into M. If A is empty, enqueue
        L in B and go to 8.
   7.3. Try to dequeue from A into R. If A is empty, enqueue
        L and M in B and go to 8.
   7.4. We've shifted the window; go to 4.

8. A is empty. Reload it from B:
   8.1. Try to dequeue from B into L. If B is empty, go to 2.
   8.2. Enqueue L in A.
   8.3. Go to 8.1.

This should eventually reduce the expression to a simple expression
(value op value) or a parenthesized value in A, with B empty; then
that will become a single value in B, with A empty; then that will
become a single value in A, with B empty; and that will satisfy the
condition in step 2, which will end the iteration.

Here's a simple example: "5 * (3 + 2 - 1)".

1: A={5,*,(,3,+,2,-,1,)}.
2: condition not satisfied.
3: L=5, M=*, R=(, A={3,+,2,-,1,)}.
4: condition not satisfied.
5: condition not satisfied.
6: B={5}, L=*, M=(, R=3, A={+,2,-,1,)}.
4: condition not satisfied.
5: condition not satisfied.
6: B={5,*}, L=(, M=3, R=+, A={2,-,1,)}.
4: condition not satisfied.
5: condition not satisfied.
6: B={5,*,(}, L=3, M=+, R=2, A={-,1,)}.
4: Calculate 3+2=5. B={5,*,(,5}.
7: L=-, M=1, R=), A={}.
4: condition not satisfied.
5: condition not satisfied.
6: Dequeue of A into R fails, so L,M,R are enqueued into B.
   B={5,*,(,5,-,1,)}.
8: Loop until A={5,*,(,5,-,1,)} and B={}.
2: condition not satisfied.
3: L=5, M=*, R=(, A={5,-,1,)}.

You can see how we'll shift the window along until we reduce
L=5, M=-, R=1 to 4 and enqueue it in B. That will be at step
4, with:

4: Calculate 5-1=4. B={5,*,(,4}. A={)}.
7: We don't have three elements left in A, so this step will
   result with B={5,*,(,4,)} and a branch to 8.
8: A={5,*,(,4,)}, B={}.

Now we'll shift the window along until we reduce L=(, M=4, R=)
to 4 in step 5 and enqueue it in B. In the next pass we'll
just have the simple expression A={5,*,4} and that's quickly
reduced to B={20}, which becomes A={20}, and in step 2 we see
that we have just a single value, which we return to the caller.

Actual implementation, additional error detection, rewriting
expresssions in other forms into parenthesized-infix notation,
implementing other functions, etc left as exercises for the
reader.

Also, many variations are possible. A reduction could reduce
into L and then dequeue additional elements into M and R, for
example.

And, of course, I may have made some stupid error; I haven't
actually tested this, except with a couple of simple cases on
paper.

[*]. Well, each operator has to be adjacent to its operands. That's
to avoid recursing to evaluate operands that are themselves
expressions. 

-- 
Michael Wojcik                  michael.wojcik@microfocus.com
Not the author (with K.Ravichandran and T.Rick Fletcher) of "Mode specific
chemistry of HS + N{_2}O(n,1,0) using stimulated Raman excitation".

Relevant Pages

  • RE: Threading Issue
    ... one might have multiple threads ... Thread-safe Enqueue and Dequeue methods (worker threads enqueue, ... Dequeue is a function returning Object. ... your main thread could just poll the queue. ...
    (microsoft.public.dotnet.languages.vb)
  • RE: [PATCH 1/2] NET: Multiple queue network device support
    ... Subject: NET: Multiple queue network device support ... repsonsible to acquire the lock for qdisc_restart. ... lock queue 1, and enqueue the packet. ... queue checked in dequeue for an skb, so I cannot rely on that lock ...
    (Linux-Kernel)
  • Re: A Queue implementation of doubly linked list in C
    ... for a broken queue and not others?" ... struct my_list* next; ... enqueue(m, "comp"); ... dequeue(m); ...
    (comp.lang.c)
  • Re: pop/push, shift/unshift
    ... on which end of the queue you were operating on. ... the array). ... have to figure out what people have aliased enqueue and dequeue to ...
    (comp.lang.ruby)
  • Re: DBMS_AQ.REMOVE issue
    ... When I dequeue a message from the queue using the DBMS_AQ.REMOVE ... In release 8.0.x when two or more processes/threads that are using ... What this means is that other consumers that need to the dequeue ...
    (comp.databases.oracle.server)