A system has a notation that would require writing an expression like (A+B)*C as #MUL(#ADD(A,B),C). Is there already an algorithm to do this kind of notation conversion so users can enter in a more conventional way?
In other words an algorithm to convert from infix -> my notation. First issue is I don't know an exact name for my notation... it's similar to reverse-polish but not quite. Every operator is encoded as a function taking arguments.
views:
79answers:
4beat me to it by 10 sec.
Randy
2010-06-16 15:42:25
+1. I've come across SY, but it's not quite the same output notation so I wondered if another algorithm was a closer match. Is this a trivial modification to the existing algorithm?
John
2010-06-16 16:03:17
Shunting yard can output abstract syntax tree. Having AST, you can traverse it pre-order to get polish notation.
el.pescado
2010-06-16 16:18:36
@John, @el.pescado: You don't really need to convert to AST. When running the RPN through the stack, instead of push back the result, we just push back the string corresponding to the expression we need. Eg. 4 2 * 5 + -> push 4,2. Now when you see *, pop 2,4 and push MUL(2,4). Now push 5. When you see +, pop 5, MUL(2,4) and result is ADD(5, MUL(2,4)).
Moron
2010-06-16 18:38:04
+1
A:
Here's some Lisp that attempts the infix -> prefix transformation. It could serve as a useful starting point.
Hank Gay
2010-06-16 15:41:49
A:
It's easy to parse these simple expressions using Lex and Yacc (of Flex and Bison, they're the same). Google for "Yacc calculator".
One example I found is http://www.indiastudychannel.com/resources/56696-IMPLEMENTATION-OF-CALCULATOR-USING-YACC.aspx but instead of calculating the results, you should build up the final string. For example, like this (pseudocode):
expr: ‘(‘expr’)’
{
$$=$2;
}
|
expr ‘*’expr
{
$$="#MUL(" + S1 + "," + $3 + ")";
}
|
expr’/’expr
{
$$="#DIV(" + S1 + "," + $3 + ")";
}
Patrick
2010-06-16 15:42:07
All well and good but I want to put this in my code, and even if it's available I don't really want to add an entire library dependency for one thing.
John
2010-06-16 16:04:44
Lex and Yacc only need the standard C library I think. I use it in my application to parse rather complex files, and running Lex and Yacc is part of my build process. In your case, you could try to run Lex and Yacc locally, and use the generated .H and .C files in your project. After all, Lex and Yacc just process your language description and generate rather standard .H and .C files. This shouldn't be a problem for you I think
Patrick
2010-06-16 16:52:18
A:
If you have Mathematica at hand, it does the conversion on the fly. With Mathlink you can use it as a "service"
FullForm[(a + b) * c]
gets
Times[Plus[a,b],c]
belisarius
2010-06-16 17:08:58