• Post Reply Bookmark Topic Watch Topic
  • New Topic

NumberList with PostFix Calculation Method  RSS feed

 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I need to write a calculation method for NumberListStack.

All calculation data is in the postfix format (ie 3 4 +) etc.

I wrote the below code but don't know if I am approaching it more complicated way than it needs to be..

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It would be better for you to stop and go through the process manually, with pen and paper first. The issue with your code right now is that it doesn't work, not whether or not it's complicated.
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:It would be better for you to stop and go through the process manually, with pen and paper first. The issue with your code right now is that it doesn't work, not whether or not it's complicated.


It ends up into endless loop for some reason..
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recaip Sanli wrote:It ends up into endless loop for some reason..

If you traced though your code with pen and paper, you'd probably find the reason why it does that.
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Recaip Sanli wrote:It ends up into endless loop for some reason..

If you traced though your code with pen and paper, you'd probably find the reason why it does that.


I did trace through and change the code, still while loop goes forever even below code

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's obviously a disconnect between your understanding of how the code should work and how it actually works. Describe exactly how you traced through the code and explain what you think is happening at each step. Then it will be easier to tell you which part you misunderstood.
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:There's obviously a disconnect between your understanding of how the code should work and how it actually works. Describe exactly how you traced through the code and explain what you think is happening at each step. Then it will be easier to tell you which part you misunderstood.


So when this code runs, it works with each time something new is being entered, which while is doing here.



Goes through line by line in data that has been provided as long as there is more data, it is suppose to stop when it reaches end of the file.


Then It checks if data found integer


Then save it in stack
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the String/Stream that you are feeding the Scanner with?
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recaip Sanli wrote:
So when this code runs, it works with each time something new is being entered, which while is doing here.

Goes through line by line in data that has been provided as long as there is more data, it is suppose to stop when it reaches end of the file.

hasNext() only tells you if there's another token, it doesn't deal with a whole line of input.

If you entered "3 4 +" then hasNext() will return true when the next token is "3", "4", and "+", otherwise it will return false.

Now, trace through your code again and see if you understand what happens in it when you get to the "+" token.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And remember, the hasNextXXX() methods only report whether or not there is something in the input stream that can be consumed by the corresponding nextXXX() method. Only the nextXXX() methods actually consume the input.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I says this in the doc for hasNext()
This method may block while waiting for input to scan.
When does it block and when doesn't it block?
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:I says this in the doc for hasNext()
This method may block while waiting for input to scan.
When does it block and when doesn't it block?

It looks like it can block in a private method called readInput(). Inside that method, there's a call to source.read(buf), so I think it depends on the source. If the source is an InputStream like System.in, the read method will block. If the Scanner was created with a String as its source, then you'll be calling StringReader.read() which doesn't appear to block.
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks. That makes sense.
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's going through endless loop when it comes accross a scenario I do not deal with, thrown exception. I think in the data file, first two lines data provided are like this:

--
187
   
--

Since it sends nothing and I don't throw an error it goes on forever.

I replaced hasNext with hasNextLine because it is necessary to read the data line by line.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In the code you posted, you had this: new Scanner(m_postfix) -- what is m_postfix here, a File that contains a postfix expression or a String representing the postfix expression to parse and evaluate?
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it's array number stack. Below code runs and gives some true values but some false. I don't know why it's not taking the operator properly. Result attached below.

PostFixCalculator


Result:
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another question is, how to throw exception with instance variable inside? Below code doesn't work...

 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Trick was this in the case of sending error operators

 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One of the problems (I haven't checked your program yet) is this piece of code:

Don't use '==' to compare Strings, use 'equals'. With what you have now you are lucky that the test on '45 +' passed.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:With what you have now you are lucky that the test on '45 +' passed.

I don't know about lucky... the test passed because the code threw an exception before execution could get to that bad if-statement.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OP's code, yes,  but the testing program could have done the checks in another order.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:OP's code, yes,  but the testing program could have done the checks in another order.

Not sure I follow your logic. I'm pretty sure the testing program is provided/shared across the board and has either a correct reference implementation or just hard-coded expectations which it then compares to the response it gets from running OP's code.

Anyway, you're absolutely right about the error OP made in using == instead of equals(). He's also missing one error condition as far as what I can tell from the test failure reports: "Too many operands"
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't get this test result:

Why is this not reporting RuntimeException - "Unrecognized operator: 5+" as the expected result instead? The "5+" token would make Scanner.hasNext() return true and Scanner.hasNextInt() return false.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, if this:

Then how can this be what it expects?

"---" would be taken as one token by Scanner.hasNext() just as "+++++" would be. What's the logic in expecting that "---" would be reported as not having enough operands when it's clearly not one of the recognized operators and yet have a totally different expectation for the same condition where "+++++" is an invalid operator as well? 

I'm deducing that the reference implementation must have this logic:

- if token is not an integer (Scanner.hasNextInt() is false) it must be an operator.
- pop two operands
- if can't pop two operands, report not enough operands
- match operator in jump table (switch statement)
- if operator not matched, report "invalid operator"

In my opinion, this logic results in inconsistent treatment of invalid operators in the input string and is therefore incorrect.  The check for invalid operator should be done first, then only when it has found that the operator is supported should it try to pop the appropriate number of operands from the stack.

EDIT: Same inconsistency with this one:


Here, "ddd" should be reported as an invalid operator.  It doesn't make sense to report that there's not enough operands when "ddd" isn't even a valid operation.

Additional Edit: On further analysis, I guess this test is correct since 2 3 + ==> 5 and then * is evaluated with only 1 operand on the stack. Ok, so this one should expect "Not enough operands" then...
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's another thing to support my assertion that the operator should be checked for validity before any attempt is made to pop operands from the stack. If you later on support an operator that only requires one operand, say a SQRT (square root) operator or a CBRT (cube root) operator, or % operator, trying to pop two operands prior to determining that the operator is one of these unary operators would screw the whole calculation up and result in an exception being thrown when it shouldn't.

A correct implementation of an RPN calculator should always check what the operator is, then jump to the appropriate handler method for that operator. The handler method is where you should code the logic for popping the appropriate number of operands needed by that particular operator.
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:Here's another thing to support my assertion that the operator should be checked for validity before any attempt is made to pop operands from the stack. If you later on support an operator that only requires one operand, say a SQRT (square root) operator or a CBRT (cube root) operator, or % operator, trying to pop two operands prior to determining that the operator is one of these unary operators would screw the whole calculation up and result in an exception being thrown when it shouldn't.

A correct implementation of an RPN calculator should always check what the operator is, then jump to the appropriate handler method for that operator. The handler method is where you should code the logic for popping the appropriate number of operands needed by that particular operator.


Interesting thoughts.. I attempted to come up with a solution that goes through the string provided and register as array appropriately checking all error conditions then processing it but I hit a brick wall at that end too..


 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One problem with your design is that it has a very awkward API. When an API is awkward, the implementation tends to be awkward and convoluted as well.

Here's some code that shows how I tested my calculator. The tests demonstrate the simple Calculator API that I exposed, which I think is more natural and intuitive:

I recreated most of the tests you showed but eliminated some that were redundant.
 
Recaip Sanli
Ranch Hand
Posts: 72
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks much more organized, thank you!
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And here's what the single public method in my Calculator class looks like:

Here are a couple of the private methods that I factored out:

The difference in the way these two methods are coded comes from the fact that multiplication is commutative while division is not. Same deal with addition vs. subtraction. Most of the methods in my class, which came in with a total of 99 lines of code in it, are no longer than what you see here. Only the jump table method that dispatches to the operator handling methods is relatively long.  With some refactoring of the design to reify the operations (turn them into actual objects) themselves and use a Map, that code can also be shortened considerably.

My point is that most of your code is jammed into that one long calculate() method. It's difficult to understand and its cyclomatic complexity is high so you will continue to misunderstand or worse, not understand at all, what your program is actually doing. If you don't have a full understanding of what your program is doing, then how can you change it to make it behave the way you want it to?
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I really wanted to be ruthless in my refactoring, I might even refactor that public evaluate(String) method like this:

Now, anyone who reads the evaluate() method and has a general idea of how a Reverse Polish Notation calculator works will be able to quickly see the algorithm and the probability of correctness. If you read that code out loud, someone listening to you will most likely say, "Yup, that sounds like what a calculator program should do all right."

By the way, search for jump table computing. Your long if-statement on lines 72-81 is a naive implementation. Follow that link to find examples of how jump tables (aka branching tables) are more commonly implemented.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!