Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

infix to postfix with negative numbers

 
mario tan
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 531
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pre-scan your string and partition unary operators with parentheses: -x becomes -(x) for example.
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Rick O'Shay
Ranch Hand
Posts: 531
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Rick O'Shay
Ranch Hand
Posts: 531
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
>> 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
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 531
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Maulin Vasavada
Ranch Hand
Posts: 1873
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic