Solved

evaluate an expression using a queue.

Posted on 2004-03-26
12
401 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
  • 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Suggested Solutions

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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
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 and use switch statements in the C programming language.

707 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now