aspose file tools*
The moose likes Java in General and the fly likes infix to postfix with negative numbers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "infix to postfix with negative numbers" Watch "infix to postfix with negative numbers" New topic
Author

infix to postfix with negative numbers

mario tan
Greenhorn

Joined: Mar 09, 2005
Posts: 10
Hi guys! I already have an algorithm on how to convert infix to postfix expressions but it is only limited positive numbers. My problem is:

1. How about if there are negative numbers in the infix expression.
2. Is there another algorithm for converting infix to postfix with negative numbers?
3. How then do I evaluate the postfix expression?

for example:

infix:
-4*(4+9*5+-(9+-4/2))=

postfix: ?

Please, can anyone there help me..?
Rick O'Shay
Ranch Hand

Joined: Sep 19, 2004
Posts: 531
Pre-scan your string and partition unary operators with parentheses: -x becomes -(x) for example.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
When you look at the example expression, how do you tell the difference between a subtraction operator and a negative number? There are several things to look for:

1) a minus sign immediately after another operator is probably the sign for a negative number
2) a minus sign at the beginning is also for a negative number
3) a minus sign immediately after a parentheses is for a negative number as well

Really, 2 and 3 are the same thing. There may be other situations where you can tell what the - means.

Another alternative is to require that the user separates all tokens with whitespace. In other words, they must put a space before and after each number and operator. Using this approach, the user is not allowed to put a space after the - for a negative number.

Layne


Java API Documentation
The Java Tutorial
Rick O'Shay
Ranch Hand

Joined: Sep 19, 2004
Posts: 531
I think it simpler to impose parentheses on unary opeators and you can automate that with regular expressions.

>> 1) a minus sign immediately after another operator is probably the sign for a negative number

There's no "maybe" statement in Java so this has limited value.

>> 2) a minus sign at the beginning is also for a negative number

Minus signs are not restricted to the beginning so this has limited value.

>> 3) a minus sign immediately after a parentheses is for a negative number as well

That is false so it has no value.

_________

If you have concurrent operators the right operator is either part of a two character unary operator, or it's a single character unary operator. It's a binary operator if the operator on the left is a closing parenthesis.
[ September 18, 2005: Message edited by: Rick O'Shay ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Ouch!

>>If you have concurrent operators the right operator is either part of a two character unary operator, or it's a single character unary operator.

Sounds like a solid "maybe" to me. If the original poster is not required to support multi-character unary operators (like i++) then let's assume the 2nd one is a unary operator. Maybe all after the first. Should 1----4 parse?

>>It's a binary operator if the operator on the left is a closing parenthesis.

That sounds correct to me. But I think Layne was suggesting after an open paren, which he described as just like the beginning of the expression. A binary operator can't exist without a left side (can it?) so I like Layne's assumption that it's unary. Limited value - it won't find all unary operators - is still value.

I was a music major so I never had to do this one in school. Surely this is a thoroughly studied area and someone who passed this class can help us out.

Mario, any of that helping? Raising new questions?
[ September 18, 2005: 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
Rick O'Shay
Ranch Hand

Joined: Sep 19, 2004
Posts: 531
>> Sounds like "maybe"

"Probably c" can't be coded but a, b or c can. That's the distinction.

>> I think Layne was suggesting after an open paren

If he meant open parenthesis versus "parentheses" that makes sense.

I'm sure you could manage unaries just peeking at the stack and looking ahead a character but it seems cleaner to do a little preprocessing. You generally do that anyway to remove extra whitespace 'n stuff.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Rick O'Shay:
>> Sounds like "maybe"

"Probably c" can't be coded but a, b or c can. That's the distinction.

>> I think Layne was suggesting after an open paren

If he meant open parenthesis versus "parentheses" that makes sense.

...


Yes, I did mean open parenthesis. Sorry about the confusion that caused.

Layne
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Rick O'Shay:
I think it simpler to impose parentheses on unary opeators and you can automate that with regular expressions.

>> 1) a minus sign immediately after another operator is probably the sign for a negative number

There's no "maybe" statement in Java so this has limited value.

...


True. However, this is not what I was implying. There is also the possibility this is a syntax error depending on what the next character is. That's why I used the word "probably".

Layne
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Rick O'Shay:
2) a minus sign at the beginning is also for a negative number

Minus signs are not restricted to the beginning so this has limited value.


I'm not sure how you read this conclusion into the statement I made. I don't see anywhere in my post that I said this is the ONLY possibility. In fact, quite the contrary. I listed two other situations. Even without those, this statement is still true since it is equivalent to "if the first character is a minus sign then it is the negative sign for a number". Of course, this assumes that the experssion is syntactically correct since this could also be a syntax error depending on what the next character is.

Layne

[ September 18, 2005: Message edited by: Layne Lund ]
[ September 18, 2005: Message edited by: Layne Lund ]
Rick O'Shay
Ranch Hand

Joined: Sep 19, 2004
Posts: 531
T'ing is he's trying code it and you can distinguish a sign operator from an arithmetic or logical operator using the same rule everywhere, beginning, end or otherwise. In many cases it's better to use a general rule than a set of special case rules.
Joel McNary
Bartender

Joined: Aug 20, 2001
Posts: 1821

Personally, I would just define a small language (make sure that it is LL(1)), set up a Tokenizer and a Lexical Analyzer, and parse the string that way. No confusion. However you do it, though, it doesn't seem to be beginner-level stuff to me (especially if you do it my way), so I'm moving this to the intermediate forum.


Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
Maulin Vasavada
Ranch Hand

Joined: Nov 04, 2001
Posts: 1871
Hi

I agree with Joel McNary. The best way would be to write a grammer(language) and go from there.

Also the other simple solution would be if you can enforce the spacing etc in the expression in such a way that,
1. Every token is separated by spaces.
e.g. ( a * ( b + c ) )
2. There is no space between the Unary operators and their operands
e.g. ( -a * ( b + c ) )

Then you can do tokenizing on space character and life should be easier.

Defining grammer would be best way. Once you define grammer you can generate the parser for the input based on that grammer via ANTLR and go from there for further processing...

Please let us know if you need more help on using ANTLR and all..

Regards
Maulin
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Originally posted by Rick O'Shay:
T'ing is he's trying code it and you can distinguish a sign operator from an arithmetic or logical operator using the same rule everywhere, beginning, end or otherwise. In many cases it's better to use a general rule than a set of special case rules.


In fact, I said just that in my original response. At least, I mentioned that #2 and #3 are essentially the same. I'm sure it could be generalized to include #1 as well.

Layne
 
Don't get me started about those stupid light bulbs.
 
subject: infix to postfix with negative numbers