This week's book giveaway is in the OCPJP forum.
We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes converting this to a prefix instead of a postfix calculator Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "converting this to a prefix instead of a postfix calculator" Watch "converting this to a prefix instead of a postfix calculator" New topic
Author

converting this to a prefix instead of a postfix calculator

Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42




This is my code but I need it to test for a prefix instead of a postfix. Is this is possible? I think it has to do with StringTonkeizer. Is there a method in that class to just test the first part instead of the last part?
[ March 01, 2007: Message edited by: Bradley Jordan ]
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Please use Code Tags to keep your code formatting intact. (You can edit your own posts by clicking on the paper & pencil icon.) Thanks!


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
I'd never seen prefix before. Guess there had to be a regular Polish notation if there was a Reverse Polish. Does this description match what you're doing?

WikiPedia shows how to solve a prefix expression by hand. Can you use the same trick to make an algorithm? Looks like you scan for two operands together, do the operation and substitute the result. Repeat.

Ha! I just made a solution with regex to find "operator operand operand" in the string and it worked the WikiPedia example exactly like they did.
[ March 02, 2007: Message edited by: Stan James ]

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
Dear Stan:
That is exactly what I need to do.I need to have all the operands in the front. How would I go about creating that alogorythm to slove it. I also have this code which I think is closer to getting a prefix calculator. Any help you could provide getting me closer would be greatly appreciated.




This is setup to check at the end for the +,/,-,*...need it check at the begining,
Thanks,
Bradley Jordan
[ March 02, 2007: Message edited by: Bradley Jordan ]
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
what is the regex? I am in need of help here..any suggestions?

Thanks,
Bradley Jordan
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

Originally posted by Bradley Jordan:
what is the regex? I am in need of help here..any suggestions?

Thanks,
Bradley Jordan


What regex? Neither of the two examples that you provided uses a regular expression to parse the tokens.

IMHO, since this is most likely a homework assignment, I think you should start from scratch, instead of from the postfix example. Working with two algorithms at once, is more of a distraction when one is still learning.

Henry
[ March 02, 2007: Message edited by: Henry Wong ]

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

Ha! I just made a solution with regex to find "operator operand operand" in the string and it worked the WikiPedia example exactly like they did.


Stan,

This sounds interesting... was it something like (in pseudo code):



I might take a crack at it later today, if I find the time...


BTW, in terms of algorithms, recursion would work here too. Something like:



Henry
[ March 02, 2007: Message edited by: Henry Wong ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
My algorithm worked on the expression as a single string:

I printed the expression each time through the loop and got this:

which was just like the example in WikiPedia.

If you get this working, think about doing it without regex. The regex feels like cheating if this is for an algorithms class. Maybe use a linked list of tokens, scan for "operator operand operand" and replace those three tokens with one result token, then scan again.

Or a little object that holds "operator operand operand" where either or both operands might be another object of the same type. That would be fun!
[ March 02, 2007: Message edited by: Stan James ]
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
I will start over...I have a question though....The user input will come in through a JOPtionPane which is a String. I can use the tonkizer to split the string up. In the examples, it is checking the last part of the token for the "+-*/". How do you check it for the just the first part of it? That is the problem I am having. Can I save each part of the string into an arry and just test the different parts of the array?

Any help would be greatly appericated.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Sounds like you are not familiar with regular expressions. They're a bit tricky, so you'll have to decide whether you want to jump into them or work with the string splitter or tokenizer. Look at Pattern in the JavaDoc and see if regex looks like something you want to learn. If you can figure out what "[+-/*] \\d+ \\d+" means in a few minutes, you're ready to go.

If not, we can probably make something with a simple tokenizer and a more complex interpreter. I'll have to think on that approach a bit longer.
Gavin Tranter
Ranch Hand

Joined: Jan 01, 2007
Posts: 333
Originally posted by Stan James:
Maybe use a linked list of tokens, scan for "operator operand operand" and replace those three tokens with one result token, then scan again.


Could you use a binary tree instead? Once the tree is constructed perhaps you could using the transverses to produce the ouput.
Not sure how you would construct the tree, sure we did an example of this back at A Level

G
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
This is just Java 101 although the instructions state write any code as long as the requirments are met so techianlly I could use the regex but since I haven't covered it but the intened way to slove it. I would like to use string tonkizer. I beleive the intened way is to use arrays. I think Is hould break the string into parts, store in a an arrya and test each part and then return the answer.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Turns out this has a very cute recursive solution. I bet that's why this format is still in circulation.

I just sketched this out here but deleted it. You'll enjoy figuring it out yourself much more than you would just reading it.

Write something that takes the simplest possible case: "+ 1 2"

Try the next case: "+ 1 + 2 3" Now when you say operand2 = getToken you get a plus sign, not a number. That looks like the start of another expression. Recursion anyone?

Those were my actual first two test cases in both versions - RegEx and recursive. I hard coded "operand1 + operand2" to keep the code simple until I was sure that the algorithm mostly worked, then put in the if/else cases for + - / *
BTW: You could do getToken() with an array or a StringTokenizer or for more modern JVMs a Scanner. Take your pick. Have fun!
[ March 02, 2007: Message edited by: Stan James ]
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

Just implemented both the regex and the recursive versions.

With the regex version, I was able to do multiple substitutions in a single pass, but there was no way to avoid multiple passes. For example, the wiki example took 5 passes. It's an elegant solution but not very efficient.

I definitely like the recursive version better. Accomplished in a single pass, and I even used a regex as the tokenizer...

Henry
[ March 02, 2007: Message edited by: Henry Wong ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
After much refactoring, I wound up with a one line "process" method:

Of course, getOperand() is more interesting than that. It's two lines.
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42


this is my code...why didn't it work....if I do the post fix 3 4 + all I get is 3.0. Please help???

[ March 04, 2007: Message edited by: Bradley Jordan ]
[ March 04, 2007: Message edited by: Bradley Jordan ]
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
[code]

import javax.swing.JOptionPane;
import java.util.*;

public class PolishNotation
{
public static void main (String [] args)
{
do
{
try
{
String getEquation = JOptionPane.showInputDialog(null, "Please enter an equation to be evaluated using Polish Notation \n" + "i.e enter +, -, /, *, first and then two numbers \n"+ "example + 3 4 for 3 + 4", "Polish Calculator",JOptionPane.QUESTION_MESSAGE);
String checkEquation = checkEquationForErrors(getEquation);
String z = doPreFix(checkEquation);
JOptionPane.showConfirmDialog(null, "The answer is " + z,"Answer",JOptionPane.OK_CANCEL_OPTION,
JOptionPane.INFORMATION_MESSAGE);
}
catch (NumberFormatException nfe)
{
JOptionPane.showMessageDialog(null, "You must enter a number for the operand", "Input Error", JOptionPane.ERROR_MESSAGE);
}
catch (NoSuchElementException mistake)
{
JOptionPane.showMessageDialog(null, "You must enter an equation to be evaluated", "Input Error", JOptionPane.ERROR_MESSAGE);
}

}
while (JOptionPane.YES_OPTION == JOptionPane.showConfirmDialog(null, "Do you want to enter another?", "Enter Scores", JOptionPane.YES_NO_OPTION));
}
public static String checkEquationForErrors(String getEquation)
{
StringTokenizer tok = new StringTokenizer(getEquation);
String s1 = tok.nextToken();
String s2 = tok.nextToken();
String s3 = tok.nextToken();

if (s1.startsWith("+")||s1.startsWith("-")|| s1.startsWith("*")||s1.startsWith("/"))
{
return getEquation;
}
else
{
JOptionPane.showMessageDialog(null, "You must enter one of these functions: +, -, *, /", "Input Error", JOptionPane.ERROR_MESSAGE);
{
return "";
}
}
}
public static String doPreFix(String getEquation)throws NumberFormatException
{
StringTokenizer tok = new StringTokenizer(getEquation);
String s1 = tok.nextToken();
String s2 = tok.nextToken();
String s3 = tok.nextToken();
String numberToString = "";
if (s1.startsWith("+"))
{
float aConvetered = Float.parseFloat(s2);
float aConvetered2 = Float.parseFloat(s3);
float z =aConvetered + aConvetered2;
numberToString = "" + z;
return numberToString;
}
else if (s1.startsWith("-"))
{
float aConvetered = Float.parseFloat(s2);
float aConvetered2 = Float.parseFloat(s3);
float z =aConvetered - aConvetered2;
numberToString = "" + z;
return numberToString;
}
else if (s1.startsWith("*"))
{
float aConvetered = Float.parseFloat(s2);
float aConvetered2 = Float.parseFloat(s3);
float z = aConvetered * aConvetered2;
numberToString = "" + z;
return numberToString;
}

else if (s1.startsWith("/"))
{
float aConvetered = Float.parseFloat(s2);
float aConvetered2 = Float.parseFloat(s3);
float z =aConvetered / aConvetered2;
numberToString = "" + z;
return numberToString;
}
return " ";
}
[\code]

this is what I was able to come up with and it works but if there is a more glamours; shorter message I am all for it.
[ March 04, 2007: Message edited by: Bradley Jordan ]
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

Bradley,

What if the user enters a expression such as "+ + 3 6 7"? That is a valid prefix expression, right?

Henry
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
yes that is a vaild expression but sure how to code for it. I tried used the alorigthium method which was further up the discussion line with the switch method but I couldn't get it working. Time is running short for me. I tried using this as my code (see below) but it wouldn't work if I do the post fix 3 4 + all I get is 3.0. Please help???
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Here's how mine started out ...

Now I can't stand duplicate code, so I moved getOperand() to its own method, factored out local variables for operand1 and operand2... 13 lines down to 1 in process:

The recursion is spread across two methods which looks a little different but works the same. I also left the input string and the array of tokens outside the recursive methods as member variables.

The process method says the expected input is operator, operand, operand. getOperand() says an operand can be a number or another expression. It's strikingly close to BNF notation for the prefix syntax. Does that seem like A Good Thing? Or is it boiled down too much?
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
Stan:

That looks a lot cleaner and nicer than what I have. I just have to explain what is happening which I can do easier with the 13 lines but I guess the shorter way is doing the same thing. I have something to had in with mine so I will not fail but I want to get an A. Will this handle something like + + 3 4 7? Thanks you so much for all help.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Yes, I tested it with "+ 1 2" then "+ 1 + 2 3" then the example from WikiPedia. Follow it through with pencil & paper to see what it does. I actually started this with pencil & paper thinking I'd use a chain of little structures holding "operator operand1 operand2" something like:

If it finds an operator in the 2nd or 3rd fields it begins another structure. When a structure has numbers in the operands we can evaluate it and plug the result back where the operator was. Try your "+ + 1 2 3" this way. It's a little trickier when there is an operator in the middle slot. Instead of prefilling the structures, we "get" tokens as we get to each slot. "+ 1 2" evaluates to 3 in the middle slot, making the first structure "+ 3 3". The "structure" turns out to just be local fields in the recursive method and then with all that refactoring, even the fields go away.

Is it fairly easy to imagine what's in getToken(), isOperator(), evaluate() and some of those other methods?
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
I understand what is goinng on...your a life safer or should I say a grade saver. To me, it was kinda of a tough assignment but to the "professionals" I am sure it was cake. I am hoping to get there. Once again, thanks a whole lot.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
You stuck with this extremely well. Hope your grades reflect the effort you put in, too. Look forward to seeing you around the ranch!
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
Stan: It won't compile...
here is my code


here is the compliler errors:

PolishNotation.java:39: cannot find symbol
symbol : method isOperator(java.lang.String)
location: class PolishNotation
if( isOperator( token ) )
^
PolishNotation.java:45: cannot find symbol
symbol : method isOperator(java.lang.String)
location: class PolishNotation
if( isOperator( token ) )
^
PolishNotation.java:50: cannot find symbol
symbol : method evaluate(java.lang.String,int,int)
location: class PolishNotation
return evaluate( operator, operand1, operand2 );

any help you could provide to get this to work, would be greatly appreciated. I thought I was done....
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
do I have to import something else. I know those function are part of the Token Class but when I try something like this...

Token tok2 = new.Token(getEquation)
can't find symbol

the isOperator and evulate are methods of that class,

any help would be gretaly appreicated,

Thanks,
Brad
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
is there anybody still reading this? Please be so I can get this running?

Thnaks?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

Bradley,

I think you have misinterpreted some of Stan's post. The goal of Javaranch is to promote the learning of Java. As such, it is the norm (policy) to "not do the homework", but to answer questions and provide (some code) hints.

Stan provided some hints to get you through the overall algorithm of what this prefix program should look like, but he didn't "do the homework". The isOperator(), evaluate(), and some other codes, were purposely left out. This is so that *you* can implement it.


BTW, I am not sure if Stan did you a favor. You can easily implement those methods (in fact, already have in this thread, in another form), without understanding how the algorithm works.

Henry
[ March 06, 2007: Message edited by: Henry Wong ]
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
Your right...I completey misunderstood...I have relooked at it and truly understand it now.

COuld you explan what isOperator is testing.

I think what is testing is if the token is a string or not...

DO I have to import anything for the isOperator to work?

Do I have to write a seperate method for it like:


public static isOperator( String token)
If (token = number)
return...

Please let me know

thanks....sorry for being such an idiot..

BRadley
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42


This is what I was able to come up with so far but it won't compile keep getting this error method:
error: /tmp/4679/PolishNotationCalculator.java:25: non-static variable partOfString
cannot be referenced from a static context
PolishNotationCalculator calculator = new PolishNotationCalculator
(partOfString);

How do I fix this?

Thanks
Brad
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Good news: Your recursive evaluate() is working fine. All it needs is a good partOfString[] array to make it go.

The error comes because your static main() method is trying to reference an instance variable. You can only reference those from non-static methods that are associated with an object instance. So let's not reference partOfString from main.

You have the whole equation, eg "+ 1 2" in the string getEquation. Why not pass that to the constructor and have the constructor split it into the partOfString array. You won't need the getToken() at all after that.

And, Yes to Henry, I went beyond our normal "hint" practices. Sorry. Guess I was just having too much fun. Fortunately, Bradley has gotten his own style very close to working. I'm betting he makes the finish line Real Soon Now.
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42

I tried passing getEquation in the PolishNotationCalculator calculator = new PolishNotationCalculator (partOfString)

it doesn't find the variable....

i created this method GetToken() and created the array there but I am not sure how to return it and than pass it to the PolishNotationCalculator calculator = new PolishNotationCalculator (getEquation)

here are the compiler errors for this one..

C:\MYDOCU~1\MYVIDE~1\PolishNotationCalculator.java:92: ']' expected
String Taxpayer [length];
^
C:\MYDOCU~1\MYVIDE~1\PolishNotationCalculator.java:101: '.class' expected
return taxpayer[];

any suggestions....
[ March 06, 2007: Message edited by: Bradley Jordan ]
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

here are the compiler errors for this one..

C:\MYDOCU~1\MYVIDE~1\PolishNotationCalculator.java:92: ']' expected
String Taxpayer [length];
^


String Taxpayer [length];

... is not valid Java code. Arrays are declared with the new operator.

C:\MYDOCU~1\MYVIDE~1\PolishNotationCalculator.java:101: '.class' expected
return taxpayer[];


Basically, you have to tell the compiler, which string object you want to return -- which element of the array.

Henry
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14688
    
  16

You should read something about arrays :
http://java.sun.com/docs/books/tutorial/java/nutsandbolts/arrays.html


[My Blog]
All roads lead to JavaRanch
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
I want to return the whole array so I can pass to it to my
PolishNotationCalculator calculator = new PolishNotationCalculator (new array)



this what I have but it is telling me that it can;t find the variable taxpayer. Any suggestions?

Stan told me to pass it the constructor which I am not totally sure if the new PolishNotationCalculator (new array) is that or if private PolishNotationCalculator (String [] partOfString)
{
this.partOfString = partOfString;
index = 0;
}
that is,...my brian is fired right now...
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18914
    
  40

this what I have but it is telling me that it can;t find the variable taxpayer. Any suggestions?


It can't find the taxpayer variable because it is out of scope. The taxpayer variable is defined in the while loop, hence, it is only valid in the while loop. If you want it accessable by the whole method, you will have to move the declaration out of the while loop.

The other issue, is that the method is declared as returning a String. If you want to return a string array, then you must change the method declaration.

Henry
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
I got it working at least returning the arrayl now how to I pass it to the
PolishNotationCalculator calculator = new PolishNotationCalculator ();
Is that possible?
Any hints..or should I go a different direction with this?
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14688
    
  16

With a private constructor, it's not going to be easy
Make it public first, and pass your array.
Bradley Jordan
Ranch Hand

Joined: Feb 19, 2007
Posts: 42
why isn't this working....I made everything public and it is return the arry, why won't it let me pass into the new instance of the Polish Calculator class...




compiler error:





/tmp/17075/PolishNotationCalculator.java:24: cannot resolve symbol
symbol : variable getEquation
location: class PolishNotationCalculator
PolishNotationCalculator calculator = new PolishNotationCalculator (getToken(getEquation));
^
1 error

any hints or suggestions would be greatly appreicated.

Thanks,,,
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Look where your String equation is declared. Is it still in scope when you create a new calculator? Google "java variable scope" if you're not sure.
[ March 07, 2007: Message edited by: Stan James ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: converting this to a prefix instead of a postfix calculator