What is easiest way to calculate an infix expression using C language?

Question

Suppose the user inputs an infix expression as a string? What could be the easiest ( By easiest I mean the shortest) way to evaluate the result of that expression using C language?

Probable ways are converting it to a postfix then by using stacks.But its rather a long process. Is there any way of using functions such as atoi() or eval() that could make the job easier?

Bagnio

changed case of title - please don't capitalise your titles, Biswajyoti Das – Thorvald

If you want the shortest, look here: #929063 – Andean

That solution doesn't do operator precedence (aka BODMAS) though -- may not be required, but I thought I'd point it out. – Ovariotomy

Answer 1

C doesn't have an "eval" function built-in, but there are libraries that provide it.

I would highly recommend using TinyExpr. It's free and open-source C code that implements math evaluation from a string. TinyExpr is only 1 C file, and it's about 500 lines of code. I don't think you'll find a shorter or easier way that is actually complete (and not just a toy example).

Here is a complete example of using it, which should demostrate how easy it is:

#include "tinyexpr.h"
#include <stdio.h>

int main(int argc, char *argv[])
{
    printf("%f\n", te_interp("5 * 5", 0)); //Prints 25
    return 0;
}

If you want to build an expression solver yourself, I would recommend looking at the TinyExpr source-code as a starting point. It's pretty clean and easy to follow.

Allout

Answer 2

Certainly the most instructive way (and possibly even the easiest, once you know how) is to learn how to write your own recursive descent parser. A parser for infix expressions in C isn't very long.

Here's one of a number of excellent blog posts by Eli Bendersky on parsing. (This one is the one that's most relevant to you, but I highly recommend all of them.) It contains source code for an infix expression parser -- admittedly in Python, not C, but the conversion should be fairly straightforward, and you'll learn a lot in the process.

Ovariotomy

Answer 3

you need to parse the string. there's no eval() in C (as in most static languages), so you need to either write your own parser or find some library to help.

since most easy to use parsers are for C++ and not C, i'd rather use a full embeddable language. my absolute favorite is Lua, which can be incredibly lightweight if you don't include the libraries. also, the syntax is nicer than C's, so your users might like it better.

of course, Lua is a full-blown programming language, so it might not be appropriate, or maybe it could help in other ways (to make it easier to extend your application).

Colossal

Here is a code fragment from my answer to a similar question that implements expression evaluation with Lua: #1157072 – Krall

If all you're doing is evaluating math expressions, Lua is not "lightweight"! Use a library made just for that purpose. – Paregmenon

Answer 4

One clean (possible not short) way to do it is to build a tree, like a compiler would.

For example, say you have the expression "2+3". The '+' would be the head. The '2' would be the left child and the '3' would be the right child.

Since each expression evaluates to a value, this tree can be extended for infinitely complex expressions: it just needs to be sorted in order of precedence for each operator. Low precedence operators (like '+' go at the top, while high-precedence operators (like '*') go at the bottom. You would then evaluate the expressions on the tree from the bottom up.

Gerlach

Answer 5

You need to build in interpreter of some scripting language.

Trovillion

Answer 6

Convert the string into an array of tokens which are the operands and operators. Convert the infix token array to a Reverse Polish Notation array. After the equation is in RPN, then you can pop tokens off the stack and operate on them.

Take a look at the Wikipedia article on Reverse Polish Notation. It shows how to do the conversion and the calculation.

Cervix