Add your own alternative version
Stats
174.5K views 3.1K downloads 63 bookmarked
Posted
2 Nov 2003

Comments and Discussions



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 Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

