I want to evaluate a mathematical expression stored as a string, eg. "1+3/4*3".
My idea to accomplish this:
Does my logic sound about right? If so, can you please show me an example even of just a basic version of like 3+1-3.
Look into the shunting yard algorithm and convert the string into reverse polish notation.
It will help if you also separate out number detection from symbol detection by reading the string one character at a time instead of just jumping to the operators.
After that, it is rather easy to perform the computation, as the inputs are ordered in a manner that makes a stack based calculator easy to implement.
Yes, you could do a full fledged recursive descent parser; but, for the relatively simple matter of algebraic expressions, they are overkill.
--- Edited because I see that there's controversy over tools vs techniques ---
I see a lot of people mentioning lexx and yacc. They are great tools, they are also overkill for what you need. It's like saying to open a carpentry shop when you want to replace a board on your fence. You don't need to learn another language to handle your math language, and lexx and yacc will require you to learn their domain specific configuration language to build the parser for your domain specific language. That's a lot of languages for a simple, solved problem.
Lexx and Yacc are great if you want to build a mathematical tree of your data; however, RPN is a mathematical tree of your data stored in a list of two fundamental node types (data) and (operation).
(a)(b)(c) // three "data nodes"
(a)(b)(+) // two "data nodes" and one operation node.
This allows one to use a stack based machine (very easy to implement). The machine has an "instruction set" of
if (x is data) { push X onto the top of the stack }
if (x is operation) {
pop the operation's required parameters.
pass them to the operation.
push the result on the stack
}
so assuming you had a '+' operator, the expression 3 + 5 + 6 would convert to RPN 3 5 + 6 + and the stack would look like (during processing)
<empty>
(3)
(3)(5)
(8)
(8)(6)
(14)
The primary reason to convert to RPN is not because it's necessary, it's because it makes the rest of your program much easier to implement. Imagine 3 + 5 * 7 converted to RPN, you have 3 5 7 * + which means that you don't have to do anything special with evaluation "machine" language. Note that (3 + 5) * 7 converts to RPN 3 5 + 7 *. In short, you reduce the complexity of the evaluation engine by massaging your input data to be less ambiguous.
Lexx and Yacc provide a lot of "configurability" to allow you to accomplish the same thing; however, you are not going to be configuring lexx and yacc to do anything special here, so the configurable interface doesn't buy you much. It's like having a multiple selection knob when you only need an on-off switch.
Now, if you want to build any kind of parser, where you are not aware of any kind of future rules which might be added; then definately choose lexx and yacc. But a simple algebraic expression parser is far too "solved" a problem to bring in the big guns. Use a shunting algorthim and break your problem down into
simple scanner to identify the main types of "tokens", NUMBER, +, -, /, *, (, and )
shunting algorithim to convert the "list" of tokens into a RPN list
a stack to hold the "memory" of the evaluation "machine"
the "machine" pull / push / evaluate loop
This has the added benefits of being able to develop the pieces independently, so you can verify each step without the entire framework being in place. Lexx and Yacc promote adding your code to their framework, so unless you take steps to do otherwise, you might have to debug the entire thing as one big piece.
You could code your own expression parser and evaluator (or interpreter), using standard recursive descent parsing techniques (then you might explicitly represent your AST). You could use standard GNU flex lexing and GNU bison parsing techniques, e.g. the infix calc example of Bison (which handles nearly exactly your example)! Or, as suggested by Edwin Buck's answer, use the shunting-yard algorithm.
(so no, your original logic does not look right!)
You might want some more powerful expressions, e.g. containing variables (like 2*x+3) or more complex things (conditionals, loops, defined functions). You'll soon want a Turing-complete language.
Then you should consider embedding some interpreter inside your program; like e.g. Lua or GNU guile. This is probably the best route (avoid reinventing the wheel, and provide the advanced user with some scripting language he might already be familiar with, and find tutorials for).
Read also about Domain Specific Languages and JIT compilation (e.g. using libjit)
See also this related question about evaluating an expression in C++.
