Add your own alternative version
Stats
348.5K views 3.2K downloads 63 bookmarked
Posted
2 Nov 2003

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
<code>
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 );
}
}
}
}
</code>
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







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.

