Solved

evaluate an expression using a queue.

Posted on 2004-03-26
12
405 Views
Last Modified: 2010-04-15
Hi,

Can anybody help me to write a program in 'c' to evaluate an expression using a queue. I am looking for the solution which does not use the concept of stack.


Any help will be highly appreciable.

Thanks in advance,
Amit
0
Comment
Question by:agri_amit
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 4
  • 2
12 Comments
 
LVL 12

Expert Comment

by:stefan73
ID: 10686104
Hi agri_amit,
I don't see how this is going to work. With a stack, you do all operations, until the stack contains only one element. But with a queue, you'll get all intermediate results as output.

Cheers,

Stefan
0
 
LVL 12

Expert Comment

by:stefan73
ID: 10686143
agri_amit,

A queue might work if you use the prefix notation for operators:

+ * 3 4 1

You'd have to pluck an operator and then the two operands, recursing when an operand is an operator.
0
 

Author Comment

by:agri_amit
ID: 10686625
Can u provide sample code for the same?
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 9

Accepted Solution

by:
ankuratvb earned 50 total points
ID: 10687566
Hi,

This link provides help on code for what u want

http://forums.devshed.com/t132345/s.html

I hope this is not a homework assignment coz it does sound like one.
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10687720
0
 
LVL 12

Expert Comment

by:stefan73
ID: 10688180
ankuratvb,
> without recursion
Yes, although the recursive approach is most straightforward - but, strictly spoken, recursion is a kind of stack itself.

The recursive algorithm looks like this (pseudocode):

double get_result(){
    queue_item operator=get_queue_item();

    if(is_value(operator)) return operator; // Simple case. Plainly return.

    // All other cases involve at least one level of operators -> out item is an operator, too.
   
    // Get left + right operand
    queue_item lo=get_result();
    queue_item ro=get_result();

    return lo operator ro;
}        
0
 

Author Comment

by:agri_amit
ID: 10701348
Yes,
ankuratvb is correct.
recursive approach itself involves stack .
Is there no way to solve it out without using stack.

Regards,
Amit
0
 
LVL 12

Expert Comment

by:stefan73
ID: 10711598
agri_amit,
> Is there no way to solve it out without using stack.

You need a stack-like logic somewhere to handle nested expressions. You have several levels and need to store them somewhere - that's the basic problem.

http://groups.google.co.in/groups?hl=en&lr=&ie=UTF-8&selm=c35oee02qod%40enews1.newsguy.com&rnum=9

This looks interesting, although it would need to be tested. The problem I see is that the second queue needs to deliver values exactly at the moment you need them as part of the logic. Could be tricky with nested expressions.


Stefan
0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10714560
Try the links,even though mine doesnt provide code but its a pretty good discussion on how
to do it.

Just a thought,Whenever u call a function,the concept of stack does come in,so how on earth would u be able to solve this without using functions.Afterall,even in a queue,u would implement ur standard push and pop functions.

I dont know about u but i think the recursion approach which is much simpler should be used.

0
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10714586
Hi stefan,

isnt your link pointing to the same thread as mine does?(i guess it does)
:~?
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

733 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question