?
Solved

evaluate an expression using a queue.

Posted on 2004-03-26
12
Medium Priority
?
407 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
Industry Leaders: 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 150 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 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

Independent Software Vendors: 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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
Suggested Courses

771 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