Solved

evaluate an expression using a queue.

Posted on 2004-03-26
12
402 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
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
logging Access violation 6 18
Converting a float to a string function in c languange 10 204
Using unmanaged DLL from managed application 14 290
Why is compiler in oracle server ? 9 44
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 how to use strings and some functions related to them in the C programming language.

912 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

21 Experts available now in Live!

Get 1:1 Help Now