|
|||||||||
|
|||||||||
| |||||||||
|
|||||||||
|
|||||||||
| |||||||||
|
|
|
| |||||||||
 |
|
|
«
Previous Thread
|
Next Thread
»
|
Thread Tools | Search this Thread | Rate Thread | Display Modes |
Dev Shed Forums Sponsor:
|
|
|
|
#1
March 20th, 2004, 02:55 AM
|
|||
|
|||
|
Solving expressions using queue..
Hi,
Can anybody suggest me how to solve a simple expressions using queue instead of stack. I have found one method. In this method if we have a expression like (a+b)*(c-d), then we convert it into a tree of form * / \ + - / \ / \ a b c d then we do a breadth-first traversal of the tree in reverse. The expression becomes dcba-+*. Now to evaluate the resulting sequence from left to right using a queue in the same way that a postfix expression is evaluated using a stack. This seems to be a very complex and lengthy method. I need some simple solution. Thanks in advance..
|
|
#2
March 22nd, 2004, 01:26 PM
|
||||
|
||||
|
Here's how I did an RPN interpreter for a language I made a few years back. (called soel)
It's probably not the most elegent way, and the language is very assembly like, but it works. I hope you can see what I'm doing here. Code:
char *soel::addmath(char *txt){
long l,a,b,s;
int c,done,o;
s=0;
a=0;
b=0;
o=0; // operand
char *endptr;
endptr=txt;
done=0;
while(!done){
c=endptr[0];
if(c == ' '){
endptr++;
//continue;
} else if (c == '('){
endptr++;
endptr=addmath(endptr);
if(o>0){addi(23+o);}
if(s==0){s=1;}
else{s=2;}
} else if (c == ')'){
endptr++;
done=1;
} else if (c == '+'){
o=1;
endptr++;
} else if (c == '-'){
o=2;
endptr++;
} else if (c == '*'){
o=3;
endptr++;
} else if (c == '/'){
o=4;
endptr++;
} else if (c == '%'){
o=5;
endptr++;
} else if (c == '^'){
o=6;
endptr++;
} else if (c == 0){
done=1;
} else if(strncmp(endptr,"pi",1)==0){
addi(11); // "addi" = add instruction
addf(3.1416);
if(s==0){s=1;a=31416;}
else if(s==1){s=2;b=31416;}
else {s=2;a=b;b=31416;}
if(s==2 && o>0){addi(23+o);}
endptr+=2;
} else if(c>='a' && c<='z'){
endptr++;
} else if(c>='A' && c<='Z'){
endptr++;
} else {
l=strtol(endptr,&endptr,10);
if(s==0){
addi(11);
addf(l);
a=l;
s=1;
} else if(s==1){
addi(11);
addf(l);
if(o>0){addi(23+o);}
b=l;
s=2;
} else {
addi(11);
addf(l);
if(o>0){addi(23+o);}
a=b;
b=l;
s=2;
}
}
}
return endptr;
}
__________________
"Science is constructed of facts as a house is of stones. But a collection of facts is no more a science than a heap of stones is a house." - Henri Poincare
|
|
#3
March 23rd, 2004, 04:54 AM
|
|||
|
|||
|
Thanks for ur reply,
From ur code i got the idea and i have been able to solve the problem using queue and recursive function.
|
|
#4
May 6th, 2004, 08:18 AM
|
|||
|
|||
|
Recursion is equivalent to stack usage
Depends a little on in what way you use recursion, but the most common way to go about this problem using recursion is equivalent to actually using an explicit stack.
|
|
#5
May 6th, 2004, 10:58 AM
|
|||
|
|||
|
Yes you are right, but this stack will be maintained and used by the OS. My requirement was not to use stack in my program. If backend applications supporting my program use the stack then it does not voilate my requirements. For this reason i droped the first idea because to do the breadth first traversal in reverse order we have to use the stack.
If you have some other idea, where we can even do away with recursion then do tell me. Thanks.
|
|
#6
May 26th, 2004, 02:05 AM
|
|||
|
|||
Reverse BFS can be obtained directly from the expression without using stack or recursion. just associate a depth variable with each token and initially set depths of all tokens to 0 and scanning the expression from left to right, now if an operator is encountered, scan to the left of it and go on increasing the depths of all the token until a lower priority operator or a ( is encountered, now scan to the right of the operator and go on increasing the depths of all tokens until a ) is encountered or a lower priority operator is encountered. when the algorithm finished, u have the depths of all the tokens as if they were in an expression tree. now just sort the token according to their depths and u have the reverse BFS of the expression.
Eg: (a+b)*(c-d) -000-0-000- when + is read -101-0-000- when * is read -212-0-111- when - is read -212-0-212- sort according to depth, u have 0112222 *+-abcd reversing 2222011 dcba-+*
__________________
IMHO 
|
|
#7
May 26th, 2004, 12:27 PM
|
||||
|
||||
|
Quote:
Why would you want to reverse it? *+-abcd becomes: Code:
* / \ + - / \ / \ a b c d if you just push it drectly into the tree Last edited by dog135 : May 26th, 2004 at 12:32 PM.
|
|
#8
June 4th, 2004, 04:05 AM
|
|||
|
|||
|
Reversing is necessary.
If we have this expression: dcba-+* Then using queue it can be solved. insert d,c,b,a all in queue. Next we get -, remove two elements from queue i.e. d and c. Apply operation -, insert result back to queue i.e. (c-d) Next we get +, remove two elements from queue i.e. b and a. Apply operation +, insert result back in quue i.e. (a+b) Next we get *, remove two elements from queue i.e (a+b) and (c-d), apply operation. You get the final output. This can not be done with the expression in the form: *+-abcd So we have to reverse it..
|
|
#9
June 4th, 2004, 04:07 AM
|
|||
|
|||
|
Jaspreet,
I am looking into the way suggested by u. I will let u know when i implement it.. Thanks.
|
|
| Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Solving expressions using queue.. |
| Thread Tools | Search this Thread |
| Display Modes | Rate This Thread |
|
|
 |
|
|
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Linear Mode
