I'm working on project for school. It has to calculate roots of non-linear function using three methods: biscetion, regula falsi and secant method. It also has to comapre standard arithmietic and interval arithmetic. For intervals, I'm using boost interval libary. After writting everything I realised that I didn't let user to input actual function (I've been using fixed cos function). How can I do such thing? I think I can't simply "transform" string input into function?
I think I should parse it into equation?
Here is how my program works.
Interval f(const Interval& function) { return cos(function); }
When using bisection my program simply use this function while for calcualtions eg:
if (f(xi) * f(przedzial.lower()) < Interval(0))
Now I would like to ask user to input it's function eg. x*x-3 or sin(x).
How can I do that?
There are several ways you may wish to solve the problem. One would be to simply provide the user a list of preprogrammed functions to choose from. This would be your quickest, easiest solution.
If you wish to supply the ability to input any algebraic expression as a function, then get ready to get nerdy. It is worth your time to Google around “Algebraic Recursive Descent Parser”. There are a lot of tutorials and example code out there to peruse beyond what I will post here.
⟶ I have waffled quite a bit about how I wish to present this, but wrapping everything in a class and writing very obvious but not particularly optimized code is what I have decided to go with, since the goal is understanding and shortness, not giving away a slick program.
// user input and program output
#include <cctype>
#include <ciso646>
#include <iostream>
// mathematical operations
#include <cmath>
// (name, value) variable lookup
#include <unordered_map>
// processing user input
#include <sstream>
#include <string>
// to report errors during processing
#include <exception>
#include <stdexcept>
template <typename T>
//-----------------------------------------------------------------------------
T string_to( const std::string & s, const char * errmsg )
//-----------------------------------------------------------------------------
// Helper function to convert a string to a value
{
T value;
std::istringstream ss( s );
if ((ss >> value) and (ss >> std::ws).eof()) return value;
throw std::runtime_error( errmsg );
}
//-----------------------------------------------------------------------------
struct environment : public std::unordered_map <std::string, double>
//-----------------------------------------------------------------------------
// An "environment" is a list of (name, value) pairs.
// For this example program:
// * We only need a single, global environment.
// * We will ask the USER for a value whenever we don't already have it.
// You can, of course, make this work any way you wish. If your expressions
// are always single variable, then you don't even need an actual lookup
// environment.
{
using std::unordered_map <std::string, double> ::unordered_map;
double & operator [] ( const std::string & name )
{
// Lookup the variable name
auto iter = find( name );
if (iter != end()) return iter->second;
// If not found, let's ask the user to supply a value
std::cout << name << "? ";
std::string s;
getline( std::cin, s );
double value = string_to <double> ( s, "invalid number" );
// Add the new value to the environment and return it
return unordered_map::operator [] ( name ) = value;
}
};
//-----------------------------------------------------------------------------
struct evaluate
//-----------------------------------------------------------------------------
// This is our parse-evaluate "function".
{
std::istream & f;
environment & env;
double result;
// The constructor does all the work
evaluate( std::istream & f, environment & env ) : f{f}, env{env}
{
result = expression();
// Make sure we have parsed it all
if (!f.eof())
throw error( "expected operator" );
}
// And this returns the result
operator double () const { return result; }
protected:
// This is just a friendly helper to construct a useful error message
std::runtime_error error( const std::string & s )
{
std::ostringstream ss;
f.clear();
ss << s << " at index " << f.tellg();
return std::runtime_error( ss.str() );
}
// An input stream can be thought of as a list of tokens. For an algebraic
// expression parser those tokens are pretty simple: numbers, names, and
// single-character things like '+' and '('. For this particular tokenizer,
// we will ignore all whitespace.
//
// An "accept" function recognizes whether the next available input is the
// desired token. If yes then the token is extracted.
bool accept( char c )
{
f >> std::ws; // skip whitespace
if (f.peek() != (unsigned char) c) return false;
f.get();
return true;
}
std::string extract_name() // reads tokens like "abc"
{
std::string s;
int c = f.peek();
while (!f.eof() and std::isalpha( (unsigned char) c ))
{
s += (char) f.get();
c = f.peek();
}
return s;
}
bool accept( const std::string & name )
{
auto pos = f.tellg();
if (name == extract_name()) return true;
f.clear();
f.seekg( pos );
return false;
}
// Now for our expression grammar.
//
// expression ::= term (add_op term)* add_op ::= '+' | '-'
// term ::= factor (mul_op factor)* mul_op ::= '*' | '/' | '%'
// factor ::= '-'? leaf ('^' factor)?
// leaf ::= number | function | variable | parentheses
// function ::= name parentheses
// parentheses ::= '(' expression ')'
//
// This grammar is very simple. Even so, it:
// * It handles unary negation properly
// * Exponentiation ('power') is RIGHT-associative (many languages
// associate it to the left, even though in real math it is right)
// * It handles named unary functions.
//
// What follows is our parser functions, which are really little more than
// the expression grammar above.
double expression()
{
double lhs = term();
while (true)
if (accept( '+' )) lhs = lhs + term();
else if (accept( '-' )) lhs = lhs - term();
else break;
return lhs;
}
double term()
{
double lhs = factor();
while (true)
if (accept( '*' )) lhs = lhs * factor();
else if (accept( '/' )) lhs = lhs / factor();
else if (accept( '%' )) lhs = fmod( lhs , factor() );
else break;
return lhs;
}
double factor()
{
double sign = accept( '-' ) ? -1 : 1;
double lhs = leaf();
if (accept( '^' )) return sign * pow( lhs, factor() );
else return sign * lhs;
}
double leaf()
{
// number
double value;
if (f >> value) return value;
f.clear();
// function
if (accept( "sin" )) return std::sin( parentheses( "expected '('" ) );
if (accept( "cos" )) return std::cos( parentheses( "expected '('" ) );
if (accept( "tan" )) return std::tan( parentheses( "expected '('" ) );
if (accept( "log" )) return std::log( parentheses( "expected '('" ) );
// variable
auto name = extract_name();
if (!name.empty()) return env[ name ];
// parentheses
return parentheses( "expected number, function, variable, or '('" );
}
double parentheses( const char * errmsg )
{
if (accept( '(' ))
{
double value = expression();
if (!accept( ')' ))
throw error( "expected ')'" );
return value;
}
throw error( errmsg );
}
};
//-----------------------------------------------------------------------------
int main()
//-----------------------------------------------------------------------------
try
{
// Ask the user for the expression to evaluate
std::string expression;
std::cout << "Expression? ";
getline( std::cin, expression );
// Initialize our environment. Remember, our environment is
// special: it will ask the user for values it does not know!
environment env = {{ "pi", 3.1415'9265'3589'7932 }};
std::istringstream stream( expression );
double result = evaluate( stream, env );
std::cout << "result = " << result << "\n";
}
catch (const std::exception & e)
{
std::cout << e.what() << "\n";
return 1;
}
You will observe that the code is divided into several sections:
The parsing functions are where the magic of RD happens. Notice that the BNF(-esque) grammar and the functions themselves are really very much the same thing! The structure of this grammar is what gives the parts of the expression both
The terminal expression (what I have called “leaf” in the code) is where things either wrap around (the recursive bit) or expect a final node (a number or variable name).
As you can see, recursive descent is capable of evaluating an expression at the very same time it is parsing it. This is one of its (many) strengths.
However, it is significantly more efficient, particularly if you have an expression you wish to evaluate multiple times, to use recursive descent to create an Abstract Syntax Tree.
An AST is a tree structure with nodes that looks like this:
struct AST
{
node_type type;
std::string name; // variable or function name
std::vector <AST> children;
};
That is, you can use RD to easily parse (4+n)*2 into a tree that looks like:
(*)
| \
(+) (2)
| \
(4) (n)
Evaluating an AST tree will always be faster than re-tokenizing and parsing a string. Whether your needs see any difference is another thing.
⟶ Notice, in particular, the code to extract/accept function and variable names I present above is especially redundant. I can think of about four different ways to significantly optimize it off the top of my head, but at the expense of making the parser itself a little less obvious a reading.
If you wish to build an AST, you will see that it is near identical code to evaluating the expression.
For example, the expression() function might become:
AST expression()
{
AST lhs = term();
while (true)
if (accept( '+' )) lhs = AST( AST::add, lhs, term() );
else if (accept( '-' )) lhs = AST( AST::subtract, lhs, term() );
else break;
return lhs;
}
The nice thing about an AST is you can also apply all kinds of optimizations to it. (But that is likely waaay beyond anything you wish to bother with.)
The “environment” is a term for the variables the expression may use. As noted in the code, you may not actually need one. Require the user to use x as a variable name (or treat any variable name the user uses as the variable name).
⟶ Again, I waffled a bit on whether or not to include an environment table at all, simply because it makes the code less succinct, but I think that including it is useful knowledge that shouldn’t be forgotten when dealing with parsing expressions containing user-variables. Things get more interesting when you add the idea of scope, but I will continue to completely ignore that.
The environment need not be limited to one kind of variable. For example, it could be made to include all the functions we use (like sine and cosine, and even user-functions). This would be yet another massive optimization. For a one-off school project, though, you could just pretend it doesn’t exist.
Things to try:
4 + 3 * 2
(4+3) * 2
-cos(pi)
pi*r^2
4^3^2
(4^3)^2
-7^2
x + 2*y
((3))
You can also try typing in malformed expressions, like:
12+
---3
( )
)9
3 2 1
-4**k
Remember, this is code you are finding on the internet. The purpose of the code is to give you something to play with and modify (significantly) to help meet your needs.
You will find that recursive descent parsers all kind of look the same. RD is a very straight-forward design. In particular, the functions should look very much like the grammar.
Being able to think through how a grammar works to manage an algebraic expression is what is important. For example, what about the grammar (and the functions that implement it) make addition left-associative? That is, 1 + 2 + 3 really is parsed and computed as (1 + 2) + 3. Why? What makes exponentiation right-associative? What makes unary minus not collide with subtraction?
(For extra educational content, can you find the “bug” with negative number inputs? One of the error examples I gave you above hints at it. Here is another hint: I use f >> value without first checking to see if the next token starts with a digit. How does that permit the weirdness?)
This has been a much larger post than I wanted, but the way to implement “convert input string into function” is really not a one-liner kind of subject. Here there be dragons. Literally.
This post, while large for an internet answer, is actually fairly short and sweet (as best I can get it without being useless), and designed to hopefully whet your appetite for this kind of cool stuff.
It is totally okay if you instead say to yourself, “Self, all that stuff is madness! Run away!” 😃
Sorry it took so long. Yesterday was Mother’s Day here in the US and I spend the evening with my family. Also, it took me a couple hours to whip this little code up into something I considered presentable.