I didn’t mean to imply that I wasn’t using the shunting yard algorithm. I am using it for the final conversion of successful postfix expressions to infix. However, the problem of converting from postfix to infix is relatively minor compared to the generation of the postfix expressions themselves. Where the earlier version of the program generated all of the expression permutations in infix, the new version generates all of the permutations in postfix for better efficiency. I thought this would be much easier to implement, but the permutation generator became more involved than I had anticipated.
The parentheses problem that I mentioned in my previous post seems to be resolved now. It had worked fine when dealing with operators of different precedence, and added parentheses correctly. But when dealing with operators of the same precedence which have Left Associativity (eg., subtraction, division, exponentiation) it would fail. For example, the postfix expression
4 3 2 1 - - -
would incorrectly convert to the infix expression
4 - 3 - 2 - 1
when it should have converted to
4 - (3 - (2 - 1))
Anyway, the infix conversion seems to be working correctly now, but I haven’t yet tested it exhaustively.
No I haven’t. I don’t see how there could be an analytical approach, since there are typically hundreds of solutions to the problem. I’d be interested in how you would approach this.
As I promised, I’ve uploaded the project, for anyone who is interested: My project
Any suggestions on improving efficiency are gratefully accepted.
I’ll post a final note on this, because I found another problem in my infix converter related to the parenthesizing of expressions containing exponents. Exponents should have right associativity, but I had been testing the output of my infix converter by pasting the resulting expression into a LibreOffice spreadsheet to confirm that it gave the correct value when it evaluated the expression. In some cases it gave different results than what I expected, and I assumed that I’d made a mistake in the infix converter. So, I changed the exponent operator to left associativity, and then everything that I pasted into the spreadsheet agreed with the expected value. However, I was still suspicious, and doing some hand calculations with simpler exponent expressions, I realized that LibreOffice doesn’t evaluate exponents in the correct order (at least not as generally accepted in mathematics textbooks). So, I changed exponents back to right associativity, and it’s now producing correct expressions even though LibreOffice doesn’t necessarily like them.
To explain with an example, the expression a^b^c should be evaluated as a^(b^c). The postfix expression a b c ^ ^ is converted by my infix converter to a^b^c and doesn’t add the parentheses since they should be unnecessary. However, LibreOffice evaluates a^b^c as if it had been parenthesized as b^c[/b] which is incorrect. So, just a word of warning never to trust the evaluation order of spreadsheet program when testing your own software.
I’ve uploaded the revised version of the project with this correction and a few other minor changes, at the same link as in my last post.
If ^ is meaning a specific operation (exponentiation like in Xojo), then it is of left-to-right associativity as in LibreOffice. Same goes for all algebraic operators.
Yes, it is exponentiation, and none of my math resources agree with LibreOffice’s method of evaluation.
For example, if you refer to the wikipedia article: https://en.wikipedia.org/wiki/Order_of_operations
and scroll about halfway down the page to “Special Cases” it specifically mentions that Microsoft Excel evaluates exponentiation in the wrong order, and that LibreOffice decided to do it the same (wrong) way, in order to maintain compatibility with Excel.
I was not speaking about math, but about the usual associativity of the power function in programming languages.
The older the language is or its ancestor the more likely it is left-to-right, with the notable exception of Fortran (which makes sense as it was developed as a number-crunching math-oriented language). ALGOL, C, C++, BASIC, and its heirs are evaluating from left-to-right, and if you count Java and other languages which do not have a power operator but a function (which means left-to-right associativity too), it is clear that 95% of all programs written use a power operator or function with left-to-right associativity.
The Pow function seems to be used in all languages using C style syntax. It’s also used in Java and Javascript. It’s quite cumbersome if you’re doing a significant number of mathematical calculations.
Surprisingly, I hadn’t even thought about checking exponentiation evaluation order in Xojo. Like most people, when I enter expressions in program code and into spreadsheet, I almost always add parentheses just to be sure that things evaluate the way that I want them to.
I guess to be completely practical, the way an expression should be formatted depends on its intended use. The way that I now have the infix converter set up (tinkered with it again last night), it’s a simple matter of setting several configuration variables at the beginning of the converter routine, which I now do with a select case construct. So one routine can switch between ‘Math Textbook’ infix, Excel infix and LaTeX markup.
Yes. I’m aware of it, but have not used it because of its cost. As I recall, there is a free web version but the amount of computing time available for a single problem is very limited. I do use Octave and Maxima though.
BTW, as someone who has been into scientific/engineering programming since the 1970’s, I’ve developed a mindset about certain types of problems that should not be attempted due to lack of computing power. However, as Moore’s Law marches on, many of these old problems are now perfectly feasible for solution on a modern computer. I’m very impressed when I look at the statistics from my program and see a million expression evaluations in less than a second. It seems rather sad to me that so much of this processing power ends up being wasted on making an animated user interface.
I looked at your code. I’ve coded similar solutions for other polynomials (i.e. give all the factors that make 53) The speed is impressive indeed, but it is not really heavy in computation. The calculation itself is lightweight. It’s the amount of iterations that is heavy. Nice coded though!