Archived

This topic is now archived and is closed to further replies.

Utuk Xul

[java] Postfix notation - beginner question

Recommended Posts

Utuk Xul    122
Hey all, I am working on a program that will take an input string in postfix notation and will spit out the answer. I know using a stack is the best data structure for this. But, I am having a hard time with one part. How can I seperate the operand from the operator in the input string? I am using a string tokenizer, but when I get that token I am not sure how to go about identifying it. I tried to use several different pieces code but they were bulky and/or impractical. Does anyone know of a method in the String class that can save me this headache? Thanks in advance

Share this post


Link to post
Share on other sites
jermz    122
What's the difference between operands and operators? One is a number and the other is a special symbol that specifies some type of math operation. All you need to do is check if your token is an operand (number) or an operator (special symbol KNOWN by you). If its not, you have an error. Otherwise just do what you're supposed to do. I would test for a token being an operator first. That way you won't be getting NumberFormatExceptions when your token is a valid operator.

Who cares if the methods you used to determine type were bulky as long as their interface was simple. Thats why people are able to write computer programs.

Every new programmer writes a function to convert a string representation of a number into the actual value. It's good for the soul. Then they wise up and use atoi() or Integer.parseInt().

EDIT: Fixed my dyslexia

[edited by - jermz on January 29, 2003 2:43:13 PM]

Share this post


Link to post
Share on other sites
IllMind    122
quote:
Original post by Utuk Xul
How can I seperate the operand from the operator in the input string? I am using a string tokenizer, but when I get that token I am not sure how to go about identifying it.


Hi Ive done some similar projects for my CSC Data Structures class using stacks, then we did the same thing with binary trees (they allow you to convert from post, pre, an infix notation). Anyways I would like to help you but im a bit confused. Have you successfully parsed the string and stored the tokens in the stack?? Or is that where your stuck?? Tell us excatly where you are having problems (parsing or evaulating). As far as determining what a token actually is, thats not needed until you beging to evaluate the stack. At that point you can check what a token is by tossing it through a switch statement which can identify all your tokens (im assuming... + - * / number... and maybe ^ or some others)

Share this post


Link to post
Share on other sites
Utuk Xul    122
Thanks for the replies,

I parsed it successfully but my evaluation is where I was confused. My confusion stemmed from what exactly the token is. I am pretty sure it is still a string so I used a switch case using .equals(+ * / -) and then doing the necessary operations.
It just seems to me that there is a more efficient way than a switch to do this operation. For instance is there something like a .doesNotEqual (I did not see it in the Javadoc)and could I be able to put all operators in one if statement? (told you I was a beginner!)

Share this post


Link to post
Share on other sites
IllMind    122
Well, first off I dont really think you need to worry about efficiency all that much. You said you are a beginner so a few extra milliseconds difference between a switch statement and some sort of conditional ''if'' statement really wont matter (if there even IS a difference). All those switch and if statments are all translated into cmp (compare) and jmp (jump) machine code anyways. I used to be super concerned about effiency of execution too until i realized aka learned that efficency can be broken up into many catagories (execution, matenince time, developing time, ect.). But if you prefer to use a .NotEquals(), remember your boolean operators. for instance you could say...

if( !(token.Equals("+") || token.Equals("-") || token.Equals("*") || token.Equals("/") ) )

which is basicly your .NotEquals( + - * / ) deal


Share this post


Link to post
Share on other sites
Fruny    1658
Create a dictionary (any type of associative array, hash table...) mapping your operators to the functions they execute. Strings in the dictionary are operators, anything else is a value.

When parsing, if a (valid) token is in the dictionary, then you execute the associated operation and push the result on the stack, otherwise, you just push the symbol on the stack.

Once you add a command to insert/remove tokens from the dictionary, and a call statement which runs the interpreter on a string on the stack, you''re only inches awayfrom having reimplemented a language such as Forth or Lisp

This simplicity is what makes prefix and postfix notations attractive.


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Share this post


Link to post
Share on other sites