
Comments and Discussions



Hello
Sorry your question is not clear.
> is rpn neans postfix expression too?
If you read the article, that what the first line says.





Thanks for this, Elias. I've learned quite a bit from it. A suggestion: Get rid of the std::string. It slows this code down quite a bit (try stepping through it with F11 instead of F10). =(





Hello
Thanks for your comment.
The code is outdated and just for educational purpose.
Please feel free to modify as you like.
Regards,
Elias





I think the use of std::string is fine  the only problem is that many functions pass the strings by value rather than by reference, e.g. isOperator(string op) would be much more efficient as isOperator( const string & op ).
Other than that this is a very handy example  thanks.
Paul





When I try to make this operation:
23!=1
I get an "eval_invalidoperand"
Could anybody tell me what I´m doing wrong?I want to check if 23 is different of 1.
Thank you.





Hello
This is a bug, it seems I forgot to include the "!" in the op[0] list, add it as:
{"!<>=*/%+^&\\", 1}, // Operators[0] is reserved for storing all symbols that can be used in operators
Regards,
Elias





I've been trying to figure out a way to handle cases such as these:
2^2=4 and 2^2=0.25
In the first case the exponentiation operator has precedence but in the second case the negation operator has precedence. This must be handled when converting from infix to postfix. Is there a simple solution to this problem. There are, of course, many ugly ways to solve thisjust hoping for one of those solutions that makes me say "Now why didn't I think of that?"





Hello there,
A quick fix would be to create two operators the "^" and "^" and two different handlers.
You handle the first as postive exponent while the second a negative exponent directly though the input number will be positive since the "" will be part of the "^" operator.
HTH
Elias





Hadn't thought of using two different operators...
...anyway, here's how I solved it: while converting from infix to post fix when a '^' is on the top of the stack and a '' (negation) is the current token, push it (negation operator) onto the stack. Otherwise, do everthing as described in the psuedo code.





This is pretty cool and is a great learning tool, however this doesn't take floats for inputs (it will only handle integers). To change this, get rid of the cast to (long) in evaluateRPN in the "// not an operator" block. Instead, cast d to type T when pushing it onto the stack.





snip
// not an operator
if (idx < 0)
{
tokenLen = getToken(rpn.substr(i));
token = rpn.substr(i, tokenLen);
char *errstr;
double d = strtod(token.c_str(), &errstr);
if (*errstr)
return eval_invalidoperand;
r = d;
st.push(r);
i += tokenLen  1;
continue;
// not an operator
if (idx < 0)
{
tokenLen = getToken(rpn.substr(i));
token = rpn.substr(i, tokenLen);
char *errstr;
double d = strtod(token.c_str(), &errstr);
if (*errstr)
return eval_invalidoperand;
r = d; // < (A)
st.push(r);
i += tokenLen  1;
continue;
I tested the code again and it supports floats evaluation.
cccMangus wrote:
, cast d to type T when pushing it onto the stac
Check the line (A).





It most certainly doesn't work on my platform without the cast (nor should it  the cast should be required in terms of C++ compliance), but I'm guessing its compiler related. I'm compiling with .NET 2003 (98% compliant). That said, with the fix, it works most excellent. Thanks for this! It saves me quite a bit of time. =)





How about writinh sin, cos, log, and other math functions?





I intend to implement some single operand operation (
such as sin(), abs() etc) into this module, would you have
time to hint me the directions? As the code is doing char by
char, odinary form "ABS()" might be out of the question?
Thank you and Best wishes!
Kevin,





I did a rewrite of this code some time ago, and have added functions as well as variables. If you are interested, take a look here[^].
 modified at 9:28 Saturday 8th October, 2005





Hello
Kevin: Don't know if RPN can handle functions (especially in the way it parses), however I can think of writing a simple expression parser/evaluator (not RPN) based.
Just saw Stephane's article and it looks nice and well designed, I can safely recommend it!





Thank you two for the quick reply. I will dive into Stephane's Eval first.
Thanks again, and wish you two Happy New Year.
Kevin.





I think there are some problem in Stephane's source code.
In method
BOOL wzparser::parse(LPSTR szFormula)
{
while ( *p )
{
if (!existingop)
{
m_arroperators.Push( op ); }
else {
if ( op>isHigherPriorityThan(existingop)  existingop>getID() == PARENTHESISID )
{
m_arroperators.Push( op );
}
else
{
existingop = m_arroperators.Pop();
m_arrelements.Add( existingop );
m_arroperators.Push( op );
}
} }
}
The code just pop the first operator(op1) that has higher priority than current operator(op0), but perhaps after pop(), the m_arroperators's top operator(op2) still has higher priority than op0,(priority(op0) < priority(op2) < priority(op1)) then the code handle the case incorrectly.





Our enviroment requires strict ANSI C, so I prob still have to try to tweak lallous's code. I plan to use "[,]"
to subsitue "ABS(,)". Once [ is encounted, will perform
push stack, mostly like "(". and when found "]", do as ")" and also insert an "A" into operand stack.
And in evaluating stage, when found "A", pop out the stack and perform the calc. I hope this will work; but then again the short comming is this method can only be used on very limited number of extra functions.
Kevin.





Hi folks,
I am working on a homework and was wondering whether anyone could hepl out.
I am to write a C++ code for evaluating the Reverse Polish Notation (using Stacks) and have program output the process in machine language:
say
LOAD 6,
ADD 10,
STORE RESULT1
SUB 2
MULT 4
STORE RESULT2
Hope someone can help me with this.
Thanks





Hello,
The article's code shows how to:
1. parse infix and convert to RPN
2. how to interpret / compute the RPN expression
Start learning how the evaluate() works and there you can instead of directly computing you can output machine language code.
HTH





RPN has been designed for old basic calculators.
HP is still implementing it in new ones.
Next homework.
Write the parser for infix notation  explicit  no conversion to RPN.
Expected conclusion:
1. The parser will be of the same complexity like current solution.
2. Writing the parser is piece of cake.
You can use Yacc  it will do it for you, but we want to use C++, isn't it?






Experience standing behind mathematics convinced me to standard notation and not idea of somebody that developed RPN to simplify construction of the calculator. And one more fan of the RPN will not change my opinion about RPN. There are also people who like to use abacus and they can make calculations faster than using calculator.
Hint questions: 1. How to make matrix calculation using RPN? i.e. [[1,2,3],[4,3,4]]*[[2,3],[4,4],[1,4]] hint: does it possible? That's why the normal notation parser is open for extending the functionality and the RPN parser is not. Regardless of the fact that writing normal notation parser is not more difficult.
2. How much time RPN familiar person needs to say the results of the expression below? RPN notation: 2.5 3 E sin 2 ^ 2.5 3 E cos 2 ^ + Standard notation: sin(2.5E3)^2+cos(2.5E3)^2 hint: I did this test for few my friends whose were fans of the RPN giving to one of them 10 such expressions writen in RPN and to the other same expressions in standard notation . This test have shown them that they were loosing their time by using RPN.
Finally The Code Project is the place where many developers learn to improve their skills in programming. LET'S NOT GIVE THEM BAD EXAMPLES.





Of course you are right: RPN is minor to standard notation, but for me it works fine. I know I shoulod not think in this way but for me RPN works faster, because I am just used to it. So probably the code in this article can be useful to me (and to your friends who still use RPN).
Nevertheless, Code Project sometimes is also a place (at least for me) for people to learn things beyond simple programming. In my oppinion it is not really bad for someone to know how RPN works.
Timo





I agree with you  about the RPN and Code Project.
I would like to clearify my opinion about this particular article. Especially what is bad in this example: Bad is the way of solving the problem. The task is: Write evaluator class for infix (standard) notation. The proposed solution is: Convert the infix to RPN, then evaluate RPN expression. The error is conversion from infix notation to the RPN. Why: Stadard infix notation, as I wrote in previous post, allows to express much more complex expressions. The RPN is pure notation designed for simple calculators (without CPU onboard, only ALU and two stacks for arguments & operations, and control logic).
Additionally my programming experience is that writing the explicit parser for infix notation is not more difficult task than writing parser infix>RPN>evaluate RPN.
Best regards





Hi,
Guess that is on my list too, don't know when my time allows but been curious to learn and design such a solution partially on my own (knowing that many wrote such code and papers).





The expression evaluator chokes on "(((1 + 1) + 1) + 1)". If I have time to look into this I will and let you know what's wrong. If I had to guess right now, I'd say that the expression evaluator doesn't like parenthesis being the first thing in the string to be evaluated.
Also, if the expression evaluator comes across something like "hello" in the string, it treats it as zero. It would be nice if the expression evaluator would return an error on this.





After a quick scan of the source, it appears to me that the hyphen's being interpreted as an operator instead of a minus sign. The error being thrown is probably due to there being too many operators for the number of operands.
Thank you.
Jeff Varszegi





Hello Kevin,
Thanks for the report.
Yes, I can guess why it chokes...cause '1' is not a binary operation, 01 would solve it currently.
I will support that and update the code.





Thanks, that makes sense.
And about creating a failure on on expressions like "hello" instead of evaluating those to zero, you can change some code in the template function evaluateRPN() from:
// not an operator
if (idx < 0)
{
tokenLen = getToken(rpn.substr(i));
token = rpn.substr(i, tokenLen);
double d = atof(token.c_str());
r = d;
st.push(r);
i += tokenLen  1;
continue;
}
to:
// not an operator
if (idx < 0)
{
tokenLen = getToken(rpn.substr(i));
token = rpn.substr(i, tokenLen);
double d;
std::istringstream os(token.c_str());
os >> d;
if (os.fail()) return eval_evalerr;
r = d;
st.push(r);
i += tokenLen  1;
continue;
}
Of coarse you will need to include at the top of ExpressionEvaluator.cpp.
Also I think you could improve performance a little bit by changing the "string" arguments to "string&" arguments in the functions calculate() and evaluateRPN(). I haven't tested this yet though, so at this point it is just a guess.
Regards,
Kevin





 quote 
Of coarse you will need to include at the top of ExpressionEvaluator.cpp.
Also I think you could improve performance a little bit by changing the "string" arguments to "string&" arguments in the functions calculate() and evaluateRPN(). I haven't tested this yet though, so at this point it is just a guess.
 end quote 
If you're looking for speed I would suggest rewritting this w/o using STL at all! By using your own simple stack class and char pointers as your strings.
Regards,
Elias





Fair enough, however changing "string" to "string&" is a fairly simple and lowrisk optimization.





Oh, and one more thing. I noticed with "(((1 + 1) + 1) + 1)" that the program choked due to an unhandled exception. I would like to sugguest inserting a try/catch in the body of calculate() and return eval_evalerr if an exception is caught.





On and in case I didn't make it clear before, I really appreciate this article. It met a need of mine (well except for identifying negative numbers) at just the right time. I have given you a 5 and still support that rating!





Hello Kevin,
Thank you for your support and your testing.
Hopefully some issues are solved now, but waiting till the updates are reflected on CodeProject.
Regards,
Elias





I appreciate how easy this is to use and how it can be easily extended. Though it has a few limitations, it meets my current set of needs!





You could simply use reflection to compile your expression ?
Jonathan de Halleux.
www.pelikhan.com





I don't know about Reflection, however a quick look reveals that it is part of .NET and not standard C++.
Besides this article provide code and representation of the old RPN notation.





lallous wrote:
that it is part of .NET
True
lallous wrote:
Besides this article provide code and representation of the old RPN notation.
Good work, I did a LED calculator in Win32 back in '95 however the calculation engine was as elegant as yours. I would allow infinite level parenthesis and add intrinsic functions eg. Pow Sqrt etc.







General News Suggestion Question Bug Answer Joke Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

