From 40939b3ebe359b19cc4ee1d9a7b831fada71ce75 Mon Sep 17 00:00:00 2001 From: Hannes Schulze Date: Wed, 3 Jul 2024 15:05:18 +0200 Subject: implement a parser for mathematical expressions --- src/services/quick-answers/math-parser.c | 336 +++++++++++++++++++++++++++++++ 1 file changed, 336 insertions(+) create mode 100644 src/services/quick-answers/math-parser.c (limited to 'src/services/quick-answers/math-parser.c') diff --git a/src/services/quick-answers/math-parser.c b/src/services/quick-answers/math-parser.c new file mode 100644 index 0000000..bb94a66 --- /dev/null +++ b/src/services/quick-answers/math-parser.c @@ -0,0 +1,336 @@ +#include "services/quick-answers/math.h" + +typedef struct _Parser Parser; + +struct _Parser +{ + FoobarMathToken const* tokens; + gsize tokens_count; + gsize position; +}; + +typedef enum +{ + INFIX_PRECEDENCE_INVALID = -1, + INFIX_PRECEDENCE_NONE = 0, + INFIX_PRECEDENCE_ADDITIVE = 1, + INFIX_PRECEDENCE_MULTIPLICATIVE = 2, + INFIX_PRECEDENCE_EXPONENTS = 3, +} InfixPrecedence; + +static FoobarMathToken const* parser_peek ( Parser const* ctx ); +static FoobarMathToken const* parser_pop ( Parser* ctx ); +static FoobarMathExpression* parser_process ( Parser* ctx, + FoobarMathExpression* lhs, + InfixPrecedence min_precedence ); +static FoobarMathExpression* parser_process_single ( Parser* ctx, + gboolean allow_sign ); +static FoobarMathExpression* parser_process_identifier ( Parser* ctx ); +static FoobarMathExpression* parser_process_number ( Parser* ctx ); +static FoobarMathExpression* parser_process_function ( Parser* ctx, + FoobarMathFunction function ); +static FoobarMathExpression* parser_process_parens ( Parser* ctx ); +static FoobarMathExpression* parser_process_sign ( Parser* ctx ); +static gboolean parser_match_identifier ( FoobarMathToken const* token, + gchar const* identifier ); +static InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ); +static FoobarMathOperation parser_operator ( FoobarMathToken const* token ); + +FoobarMathExpression* foobar_math_parse( + FoobarMathToken const* tokens, + gsize tokens_count ) +{ + Parser ctx = { 0 }; + ctx.tokens = tokens; + ctx.tokens_count = tokens_count; + + FoobarMathExpression* lhs = parser_process_single( &ctx, TRUE ); + if ( !lhs ) { return NULL; } + + FoobarMathExpression* expr = parser_process( &ctx, lhs, INFIX_PRECEDENCE_NONE ); + if ( !expr ) { return NULL; } + + if ( parser_peek( &ctx ) ) + { + foobar_math_expression_free( expr ); + return NULL; + } + + return expr; +} + +FoobarMathToken const* parser_peek( Parser const* ctx ) +{ + if ( ctx->position >= ctx->tokens_count ) { return NULL; } + + return &ctx->tokens[ctx->position]; +} + +FoobarMathToken const* parser_pop( Parser* ctx ) +{ + if ( ctx->position >= ctx->tokens_count ) { return NULL; } + + return &ctx->tokens[ctx->position++]; +} + +FoobarMathExpression* parser_process( + Parser* ctx, + FoobarMathExpression* lhs, + InfixPrecedence min_precedence ) +{ + FoobarMathToken const* op = parser_peek( ctx ); + InfixPrecedence op_precedence = parser_operator_precedence( op ); + while ( op_precedence >= min_precedence ) + { + parser_pop( ctx ); + + FoobarMathExpression* rhs = parser_process_single( ctx, FALSE ); + if ( !rhs ) + { + foobar_math_expression_free( lhs ); + return NULL; + } + + FoobarMathToken const* next_op = parser_peek( ctx ); + while ( parser_operator_precedence( next_op ) > op_precedence ) + { + rhs = parser_process( ctx, rhs, op_precedence + 1 ); + if ( !rhs ) + { + foobar_math_expression_free( lhs ); + return NULL; + } + + next_op = parser_peek( ctx ); + } + + lhs = foobar_math_expression_operation( parser_operator( op ), lhs, rhs ); + + op = parser_peek( ctx ); + op_precedence = parser_operator_precedence( op ); + } + + return lhs; +} + +FoobarMathExpression* parser_process_single( + Parser* ctx, + gboolean allow_sign ) +{ + FoobarMathToken const* token = parser_peek( ctx ); + if ( !token ) { return NULL; } + + switch ( token->type ) + { + case FOOBAR_MATH_TOKEN_IDENTIFIER: + return parser_process_identifier( ctx ); + case FOOBAR_MATH_TOKEN_NUMBER: + return parser_process_number( ctx ); + case FOOBAR_MATH_TOKEN_PAREN_OPEN: + return parser_process_parens( ctx ); + case FOOBAR_MATH_TOKEN_MINUS: + case FOOBAR_MATH_TOKEN_PLUS: + if ( !allow_sign ) { return NULL; } + return parser_process_sign( ctx ); + case FOOBAR_MATH_TOKEN_PAREN_CLOSE: + case FOOBAR_MATH_TOKEN_MUL: + case FOOBAR_MATH_TOKEN_DIV: + case FOOBAR_MATH_TOKEN_POW: + return NULL; + default: + g_warn_if_reached( ); + return NULL; + } +} + +FoobarMathExpression* parser_process_identifier( Parser* ctx ) +{ + FoobarMathToken const* token = parser_pop( ctx ); + if ( parser_match_identifier( token, "pi" ) ) + { + return foobar_math_expression_constant( FOOBAR_MATH_CONSTANT_PI ); + } + else if ( parser_match_identifier( token, "e" ) ) + { + return foobar_math_expression_constant( FOOBAR_MATH_CONSTANT_E ); + } + else if ( parser_match_identifier( token, "exp" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_EXP ); + } + else if ( parser_match_identifier( token, "sqrt" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_SQRT ); + } + else if ( parser_match_identifier( token, "sin" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_SIN ); + } + else if ( parser_match_identifier( token, "cos" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_COS ); + } + else if ( parser_match_identifier( token, "sec" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_SEC ); + } + else if ( parser_match_identifier( token, "csc" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_CSC ); + } + else if ( parser_match_identifier( token, "tan" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_TAN ); + } + else if ( parser_match_identifier( token, "cot" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_COT ); + } + else if ( parser_match_identifier( token, "arcsin" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCSIN ); + } + else if ( parser_match_identifier( token, "arccos" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCCOS ); + } + else if ( parser_match_identifier( token, "arcsec" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCSEC ); + } + else if ( parser_match_identifier( token, "arccsc" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCCSC ); + } + else if ( parser_match_identifier( token, "arctan" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCTAN ); + } + else if ( parser_match_identifier( token, "arccot" ) ) + { + return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCCOT ); + } + else + { + return NULL; + } +} + +FoobarMathExpression* parser_process_number( Parser* ctx ) +{ + FoobarMathToken const* token = parser_pop( ctx ); + FoobarMathValue value; + if ( !foobar_math_value_from_string( token->data, token->length, &value ) ) + { + return NULL; + } + + return foobar_math_expression_value( value ); +} + +FoobarMathExpression* parser_process_function( + Parser* ctx, + FoobarMathFunction function ) +{ + FoobarMathToken const* opening_paren = parser_peek( ctx ); + if ( !opening_paren || opening_paren->type != FOOBAR_MATH_TOKEN_PAREN_OPEN ) + { + return NULL; + } + + FoobarMathExpression* arg = parser_process_parens( ctx ); + if ( !arg ) { return NULL; } + + return foobar_math_expression_function( function, arg ); +} + +FoobarMathExpression* parser_process_parens( Parser* ctx ) +{ + parser_pop( ctx ); + FoobarMathExpression* lhs = parser_process_single( ctx, TRUE ); + if ( !lhs ) { return NULL; } + FoobarMathExpression* result = parser_process( ctx, lhs, INFIX_PRECEDENCE_NONE ); + if ( !result ) { return NULL; } + FoobarMathToken const* closing_paren = parser_pop( ctx ); + if ( !closing_paren || closing_paren->type != FOOBAR_MATH_TOKEN_PAREN_CLOSE ) + { + foobar_math_expression_free( result ); + return NULL; + } + return result; +} + +FoobarMathExpression* parser_process_sign( Parser* ctx ) +{ + FoobarMathToken const* token = parser_pop( ctx ); + FoobarMathExpression* result = parser_process_single( ctx, FALSE ); + if ( !result ) { return NULL; } + + if ( token->type == FOOBAR_MATH_TOKEN_MINUS ) + { + return foobar_math_expression_function( FOOBAR_MATH_FUNCTION_NEGATE, result ); + } + else + { + return result; + } +} + +gboolean parser_match_identifier( + FoobarMathToken const* token, + gchar const* identifier ) +{ + if ( strlen( identifier ) != token->length ) { return FALSE; } + + return !strncmp( token->data, identifier, token->length ); +} + +InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ) +{ + if ( token ) + { + switch ( token->type ) + { + case FOOBAR_MATH_TOKEN_PLUS: + case FOOBAR_MATH_TOKEN_MINUS: + return INFIX_PRECEDENCE_ADDITIVE; + case FOOBAR_MATH_TOKEN_MUL: + case FOOBAR_MATH_TOKEN_DIV: + return INFIX_PRECEDENCE_MULTIPLICATIVE; + case FOOBAR_MATH_TOKEN_POW: + return INFIX_PRECEDENCE_EXPONENTS; + case FOOBAR_MATH_TOKEN_IDENTIFIER: + case FOOBAR_MATH_TOKEN_NUMBER: + case FOOBAR_MATH_TOKEN_PAREN_OPEN: + case FOOBAR_MATH_TOKEN_PAREN_CLOSE: + default: + break; + } + } + + return INFIX_PRECEDENCE_INVALID; +} + +FoobarMathOperation parser_operator( FoobarMathToken const* token ) +{ + switch ( token->type ) + { + case FOOBAR_MATH_TOKEN_PLUS: + return FOOBAR_MATH_OPERATION_ADD; + case FOOBAR_MATH_TOKEN_MINUS: + return FOOBAR_MATH_OPERATION_SUB; + case FOOBAR_MATH_TOKEN_MUL: + return FOOBAR_MATH_OPERATION_MUL; + case FOOBAR_MATH_TOKEN_DIV: + return FOOBAR_MATH_OPERATION_DIV; + case FOOBAR_MATH_TOKEN_POW: + return FOOBAR_MATH_OPERATION_POW; + case FOOBAR_MATH_TOKEN_IDENTIFIER: + case FOOBAR_MATH_TOKEN_NUMBER: + case FOOBAR_MATH_TOKEN_PAREN_OPEN: + case FOOBAR_MATH_TOKEN_PAREN_CLOSE: + default: + g_warn_if_reached( ); + return 0; + } +} -- cgit v1.3.1 From 6967d26dd1841965a6e979897e282dd66e45ef5f Mon Sep 17 00:00:00 2001 From: Hannes Schulze Date: Wed, 3 Jul 2024 19:07:45 +0200 Subject: implement expression evaluation --- src/services/quick-answer-service.c | 40 +++- src/services/quick-answers/math-parser.c | 14 +- src/services/quick-answers/math.c | 355 +++++++++++++++++++++++++++++-- src/services/quick-answers/math.h | 67 ++++-- 4 files changed, 424 insertions(+), 52 deletions(-) (limited to 'src/services/quick-answers/math-parser.c') diff --git a/src/services/quick-answer-service.c b/src/services/quick-answer-service.c index 70d54b6..8071998 100644 --- a/src/services/quick-answer-service.c +++ b/src/services/quick-answer-service.c @@ -53,8 +53,9 @@ struct _FoobarQuickAnswerService GObject parent_instance; }; -static void foobar_quick_answer_service_class_init( FoobarQuickAnswerServiceClass* klass ); -static void foobar_quick_answer_service_init ( FoobarQuickAnswerService* self ); +static void foobar_quick_answer_service_class_init( FoobarQuickAnswerServiceClass* klass ); +static void foobar_quick_answer_service_init ( FoobarQuickAnswerService* self ); +static FoobarQuickAnswer* foobar_quick_answer_service_query_math( gchar const* query ); G_DEFINE_FINAL_TYPE( FoobarQuickAnswerService, foobar_quick_answer_service, G_TYPE_OBJECT ) @@ -303,6 +304,19 @@ FoobarQuickAnswer* foobar_quick_answer_service_query( { (void)self; + FoobarQuickAnswer* result = foobar_quick_answer_service_query_math( query ); + if ( result ) { return result; } + + return NULL; +} + +// +// Try to parse the query as a mathematical expression and evaluate it. +// +FoobarQuickAnswer* foobar_quick_answer_service_query_math( gchar const* query ) +{ + FoobarQuickAnswer* result = NULL; + gsize token_count; g_autofree FoobarMathToken* tokens = foobar_math_lex( query, strlen( query ), &token_count ); if ( tokens ) @@ -310,16 +324,24 @@ FoobarQuickAnswer* foobar_quick_answer_service_query( FoobarMathExpression* expr = foobar_math_parse( tokens, token_count ); if ( expr ) { - g_print( "---\n" ); foobar_math_expression_print( expr, 0 ); + + FoobarMathValue val = { 0 }; + if ( foobar_math_evaluate( expr, &val ) ) + { + g_autofree gchar* value = foobar_math_value_to_string( val ); + g_autofree gchar* title = g_strdup_printf( "= %s", value ); + g_autoptr( GIcon ) icon = g_themed_icon_new( "fluent-calculator-symbolic" ); + result = foobar_quick_answer_new( ); + foobar_quick_answer_set_value( result, value ); + foobar_quick_answer_set_title( result, title ); + foobar_quick_answer_set_icon( result, icon ); + foobar_math_value_free( val ); + } + foobar_math_expression_free( expr ); } } - (void)foobar_quick_answer_new; - (void)foobar_quick_answer_set_value; - (void)foobar_quick_answer_set_icon; - (void)foobar_quick_answer_set_title; - - return NULL; + return result; } diff --git a/src/services/quick-answers/math-parser.c b/src/services/quick-answers/math-parser.c index bb94a66..7f93552 100644 --- a/src/services/quick-answers/math-parser.c +++ b/src/services/quick-answers/math-parser.c @@ -104,7 +104,7 @@ FoobarMathExpression* parser_process( next_op = parser_peek( ctx ); } - lhs = foobar_math_expression_operation( parser_operator( op ), lhs, rhs ); + lhs = foobar_math_expression_new_operation( parser_operator( op ), lhs, rhs ); op = parser_peek( ctx ); op_precedence = parser_operator_precedence( op ); @@ -148,11 +148,11 @@ FoobarMathExpression* parser_process_identifier( Parser* ctx ) FoobarMathToken const* token = parser_pop( ctx ); if ( parser_match_identifier( token, "pi" ) ) { - return foobar_math_expression_constant( FOOBAR_MATH_CONSTANT_PI ); + return foobar_math_expression_new_constant( FOOBAR_MATH_CONSTANT_PI ); } else if ( parser_match_identifier( token, "e" ) ) { - return foobar_math_expression_constant( FOOBAR_MATH_CONSTANT_E ); + return foobar_math_expression_new_constant( FOOBAR_MATH_CONSTANT_E ); } else if ( parser_match_identifier( token, "exp" ) ) { @@ -219,13 +219,13 @@ FoobarMathExpression* parser_process_identifier( Parser* ctx ) FoobarMathExpression* parser_process_number( Parser* ctx ) { FoobarMathToken const* token = parser_pop( ctx ); - FoobarMathValue value; + FoobarMathValue value = { 0 }; if ( !foobar_math_value_from_string( token->data, token->length, &value ) ) { return NULL; } - return foobar_math_expression_value( value ); + return foobar_math_expression_new_value( value ); } FoobarMathExpression* parser_process_function( @@ -241,7 +241,7 @@ FoobarMathExpression* parser_process_function( FoobarMathExpression* arg = parser_process_parens( ctx ); if ( !arg ) { return NULL; } - return foobar_math_expression_function( function, arg ); + return foobar_math_expression_new_function( function, arg ); } FoobarMathExpression* parser_process_parens( Parser* ctx ) @@ -268,7 +268,7 @@ FoobarMathExpression* parser_process_sign( Parser* ctx ) if ( token->type == FOOBAR_MATH_TOKEN_MINUS ) { - return foobar_math_expression_function( FOOBAR_MATH_FUNCTION_NEGATE, result ); + return foobar_math_expression_new_function( FOOBAR_MATH_FUNCTION_NEGATE, result ); } else { diff --git a/src/services/quick-answers/math.c b/src/services/quick-answers/math.c index 5ec79c0..4596af2 100644 --- a/src/services/quick-answers/math.c +++ b/src/services/quick-answers/math.c @@ -1,4 +1,7 @@ +#define _GNU_SOURCE + #include "services/quick-answers/math.h" +#include struct _FoobarMathExpression { @@ -31,7 +34,7 @@ struct _FoobarMathExpression }; }; -FoobarMathExpression* foobar_math_expression_value( FoobarMathValue value ) +FoobarMathExpression* foobar_math_expression_new_value( FoobarMathValue value ) { FoobarMathExpression* res = g_new0( FoobarMathExpression, 1 ); res->type = FOOBAR_MATH_EXPRESSION_VALUE; @@ -39,7 +42,7 @@ FoobarMathExpression* foobar_math_expression_value( FoobarMathValue value ) return res; } -FoobarMathExpression* foobar_math_expression_function( +FoobarMathExpression* foobar_math_expression_new_function( FoobarMathFunction function, FoobarMathExpression* input ) { @@ -50,7 +53,7 @@ FoobarMathExpression* foobar_math_expression_function( return res; } -FoobarMathExpression* foobar_math_expression_constant( FoobarMathConstant constant ) +FoobarMathExpression* foobar_math_expression_new_constant( FoobarMathConstant constant ) { FoobarMathExpression* res = g_new0( FoobarMathExpression, 1 ); res->type = FOOBAR_MATH_EXPRESSION_CONSTANT; @@ -58,7 +61,7 @@ FoobarMathExpression* foobar_math_expression_constant( FoobarMathConstant consta return res; } -FoobarMathExpression* foobar_math_expression_operation( +FoobarMathExpression* foobar_math_expression_new_operation( FoobarMathOperation operation, FoobarMathExpression* lhs, FoobarMathExpression* rhs ) @@ -107,7 +110,7 @@ void foobar_math_expression_print( { case FOOBAR_MATH_EXPRESSION_VALUE: { - g_autofree gchar* val = foobar_math_value_format( expr->value.v ); + g_autofree gchar* val = foobar_math_value_to_string( expr->value.v ); g_print( "%s\n", val ); break; } @@ -210,6 +213,13 @@ void foobar_math_expression_print( } } +void foobar_math_value_new_int( FoobarMathValue* out_value ) +{ + out_value->type = FOOBAR_MATH_VALUE_INT; + mpz_init( out_value->int_value.v ); + out_value->int_value.decimal_places = 0; +} + gboolean foobar_math_value_from_string( gchar const* input, gsize input_length, @@ -230,9 +240,8 @@ gboolean foobar_math_value_from_string( } } - out_value->type = FOOBAR_MATH_VALUE_INT; + foobar_math_value_new_int( out_value ); out_value->int_value.decimal_places = input_length - 1 - sep_pos; - mpz_init( out_value->int_value.v ); if ( mpz_init_set_str( out_value->int_value.v, without_sep, 10 ) == -1 ) { mpz_clear( out_value->int_value.v ); @@ -242,22 +251,173 @@ gboolean foobar_math_value_from_string( return TRUE; } +void foobar_math_value_from_float( + long double value, + FoobarMathValue* out_value ) +{ + out_value->type = FOOBAR_MATH_VALUE_FLOAT; + out_value->float_value.v = value; +} + +void foobar_math_value_copy( + FoobarMathValue value, + FoobarMathValue* out_value ) +{ + *out_value = value; + + switch ( value.type ) + { + case FOOBAR_MATH_VALUE_INT: + mpz_init_set( out_value->int_value.v, value.int_value.v ); + break; + case FOOBAR_MATH_VALUE_FLOAT: + break; + default: + g_warn_if_reached( ); + break; + } +} + void foobar_math_value_free( FoobarMathValue value ) { - if ( value.type == FOOBAR_MATH_VALUE_INT ) + switch ( value.type ) { - mpz_clear( value.int_value.v ); + case FOOBAR_MATH_VALUE_INT: + mpz_clear( value.int_value.v ); + break; + case FOOBAR_MATH_VALUE_FLOAT: + break; + default: + g_warn_if_reached( ); + break; } } -gboolean foobar_math_evaluate( - FoobarMathExpression const* expression, - FoobarMathValue* out_value ) +void foobar_math_value_negate( FoobarMathValue* value ) +{ + switch ( value->type ) + { + case FOOBAR_MATH_VALUE_INT: + mpz_neg( value->int_value.v, value->int_value.v ); + break; + case FOOBAR_MATH_VALUE_FLOAT: + value->float_value.v = -value->float_value.v; + break; + default: + g_warn_if_reached( ); + break; + } +} + +gboolean foobar_math_value_add( + FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ) +{ + if ( foobar_math_value_is_simple_int( lhs ) && foobar_math_value_is_simple_int( rhs ) ) + { + foobar_math_value_new_int( out_value ); + mpz_add( out_value->int_value.v, lhs.int_value.v, rhs.int_value.v ); + return TRUE; + } + + long double lhs_float = foobar_math_value_to_float( lhs ); + long double rhs_float = foobar_math_value_to_float( rhs ); + foobar_math_value_from_float( lhs_float + rhs_float, out_value ); + return TRUE; +} + +gboolean foobar_math_value_sub( + FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ) +{ + if ( foobar_math_value_is_simple_int( lhs ) && foobar_math_value_is_simple_int( rhs ) ) + { + foobar_math_value_new_int( out_value ); + mpz_sub( out_value->int_value.v, lhs.int_value.v, rhs.int_value.v ); + return TRUE; + } + + long double lhs_float = foobar_math_value_to_float( lhs ); + long double rhs_float = foobar_math_value_to_float( rhs ); + foobar_math_value_from_float( lhs_float - rhs_float, out_value ); + return TRUE; +} + +gboolean foobar_math_value_mul( + FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ) +{ + if ( foobar_math_value_is_simple_int( lhs ) && foobar_math_value_is_simple_int( rhs ) ) + { + foobar_math_value_new_int( out_value ); + mpz_mul( out_value->int_value.v, lhs.int_value.v, rhs.int_value.v ); + return TRUE; + } + + long double lhs_float = foobar_math_value_to_float( lhs ); + long double rhs_float = foobar_math_value_to_float( rhs ); + foobar_math_value_from_float( lhs_float * rhs_float, out_value ); + return TRUE; +} + +gboolean foobar_math_value_div( + FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ) +{ + if ( foobar_math_value_is_simple_int( lhs ) && foobar_math_value_is_simple_int( rhs ) ) + { + if ( mpz_sgn( rhs.int_value.v ) == 0 ) { return FALSE; } + + foobar_math_value_new_int( out_value ); + mpz_t rem; + mpz_init( rem ); + mpz_divmod( out_value->int_value.v, rem, lhs.int_value.v, rhs.int_value.v ); + gboolean result_is_int = mpz_sgn( rem ) == 0; + mpz_clear( rem ); + + if ( result_is_int ) { return TRUE; } + foobar_math_value_free( *out_value ); + } + + long double lhs_float = foobar_math_value_to_float( lhs ); + long double rhs_float = foobar_math_value_to_float( rhs ); + long double result = lhs_float / rhs_float; + if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } + foobar_math_value_from_float( result, out_value ); + return TRUE; +} + +gboolean foobar_math_value_pow( + FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ) { - return FALSE; + if ( foobar_math_value_is_simple_int( lhs ) && foobar_math_value_is_simple_int( rhs ) && + mpz_fits_ulong_p( rhs.int_value.v ) ) + { + foobar_math_value_new_int( out_value ); + mpz_pow_ui( out_value->int_value.v, lhs.int_value.v, mpz_get_ui( rhs.int_value.v ) ); + return TRUE; + } + + long double lhs_float = foobar_math_value_to_float( lhs ); + long double rhs_float = foobar_math_value_to_float( rhs ); + long double result = powl( lhs_float, rhs_float ); + if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } + foobar_math_value_from_float( result, out_value ); + return TRUE; +} + +gboolean foobar_math_value_is_simple_int( FoobarMathValue value ) +{ + return value.type == FOOBAR_MATH_VALUE_INT && value.int_value.decimal_places == 0; } -gchar* foobar_math_value_format( FoobarMathValue value ) +gchar* foobar_math_value_to_string( FoobarMathValue value ) { switch ( value.type ) { @@ -296,3 +456,170 @@ gchar* foobar_math_value_format( FoobarMathValue value ) return NULL; } } + +long double foobar_math_value_to_float( FoobarMathValue value ) +{ + switch ( value.type ) + { + case FOOBAR_MATH_VALUE_INT: + { + mpz_t exp, integer, frac; + mpz_inits( exp, integer, frac, NULL ); + mpz_ui_pow_ui( exp, 10, value.int_value.decimal_places ); + mpz_mod( frac, value.int_value.v, exp ); + mpz_div( integer, value.int_value.v, exp ); + mpf_t f_exp, f_frac; + mpf_inits( f_exp, f_frac, NULL ); + mpf_set_z( f_exp, exp ); + mpf_set_z( f_frac, frac ); + mpf_div( f_frac, f_frac, f_exp ); + long double result = mpz_get_d( integer ) + mpf_get_d( f_frac ); + mpf_clears( f_exp, f_frac, NULL ); + mpz_clears( exp, integer, frac, NULL ); + return result; + } + case FOOBAR_MATH_VALUE_FLOAT: + return value.float_value.v; + default: + g_warn_if_reached( ); + return 0; + } +} + +gboolean foobar_math_evaluate( + FoobarMathExpression const* expr, + FoobarMathValue* out_value ) +{ + switch ( expr->type ) + { + case FOOBAR_MATH_EXPRESSION_VALUE: + foobar_math_value_copy( expr->value.v, out_value ); + return TRUE; + case FOOBAR_MATH_EXPRESSION_CONSTANT: + switch ( expr->constant.c ) + { + case FOOBAR_MATH_CONSTANT_PI: + foobar_math_value_from_float( M_PIl, out_value ); + return TRUE; + case FOOBAR_MATH_CONSTANT_E: + foobar_math_value_from_float( M_El, out_value ); + return TRUE; + default: + g_warn_if_reached( ); + return FALSE; + } + case FOOBAR_MATH_EXPRESSION_FUNCTION: + { + FoobarMathValue input = { 0 }; + if ( !foobar_math_evaluate( expr->function.input, &input ) ) { return FALSE; } + + if ( expr->function.f == FOOBAR_MATH_FUNCTION_NEGATE ) + { + *out_value = input; + foobar_math_value_negate( out_value ); + return TRUE; + } + + long double input_float = foobar_math_value_to_float( input ); + foobar_math_value_free( input ); + + long double result = NAN; + switch ( expr->function.f ) + { + case FOOBAR_MATH_FUNCTION_SIN: + result = sinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_COS: + result = cosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_SEC: + result = 1.L / cosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_CSC: + result = 1.L / sinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_TAN: + result = tanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_COT: + result = 1.L / tanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCSIN: + result = asinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCOS: + result = acosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCSEC: + result = acosl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCSC: + result = asinl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCTAN: + result = atanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCOT: + result = atanl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_EXP: + result = expl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_SQRT: + result = sqrtl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_NEGATE: + default: + g_warn_if_reached( ); + return FALSE; + } + + if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } + + foobar_math_value_from_float( result, out_value ); + return TRUE; + } + case FOOBAR_MATH_EXPRESSION_OPERATION: + { + FoobarMathValue lhs = { 0 }; + if ( !foobar_math_evaluate( expr->operation.lhs, &lhs ) ) { return FALSE; } + FoobarMathValue rhs = { 0 }; + if ( !foobar_math_evaluate( expr->operation.rhs, &rhs ) ) + { + foobar_math_value_free( lhs ); + return FALSE; + } + + gboolean success = FALSE; + switch ( expr->operation.o ) + { + case FOOBAR_MATH_OPERATION_ADD: + success = foobar_math_value_add( lhs, rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_SUB: + success = foobar_math_value_sub( lhs, rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_MUL: + success = foobar_math_value_mul( lhs, rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_DIV: + success = foobar_math_value_div( lhs, rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_POW: + success = foobar_math_value_pow( lhs, rhs, out_value ); + break; + default: + g_warn_if_reached( ); + break; + } + + foobar_math_value_free( lhs ); + foobar_math_value_free( rhs ); + + return success; + } + default: + g_warn_if_reached( ); + return FALSE; + } +} diff --git a/src/services/quick-answers/math.h b/src/services/quick-answers/math.h index 77c587a..6bc07fe 100644 --- a/src/services/quick-answers/math.h +++ b/src/services/quick-answers/math.h @@ -98,27 +98,50 @@ typedef enum typedef struct _FoobarMathExpression FoobarMathExpression; -FoobarMathToken* foobar_math_lex ( gchar const* input, - gsize input_length, - gsize* out_count ); -FoobarMathExpression* foobar_math_parse ( FoobarMathToken const* tokens, - gsize tokens_count ); -FoobarMathExpression* foobar_math_expression_value ( FoobarMathValue value ); -FoobarMathExpression* foobar_math_expression_function ( FoobarMathFunction function, - FoobarMathExpression* input ); -FoobarMathExpression* foobar_math_expression_constant ( FoobarMathConstant constant ); -FoobarMathExpression* foobar_math_expression_operation( FoobarMathOperation operation, - FoobarMathExpression* lhs, - FoobarMathExpression* rhs ); -void foobar_math_expression_print ( FoobarMathExpression const* expr, - gint indentation ); -void foobar_math_expression_free ( FoobarMathExpression* expression ); -gboolean foobar_math_value_from_string ( gchar const* input, - gsize input_length, - FoobarMathValue* out_value ); -void foobar_math_value_free ( FoobarMathValue value ); -gchar* foobar_math_value_format ( FoobarMathValue value ); -gboolean foobar_math_evaluate ( FoobarMathExpression const* expression, - FoobarMathValue* out_value ); +FoobarMathToken* foobar_math_lex ( gchar const* input, + gsize input_length, + gsize* out_count ); +FoobarMathExpression* foobar_math_parse ( FoobarMathToken const* tokens, + gsize tokens_count ); +FoobarMathExpression* foobar_math_expression_new_value ( FoobarMathValue value ); +FoobarMathExpression* foobar_math_expression_new_function ( FoobarMathFunction function, + FoobarMathExpression* input ); +FoobarMathExpression* foobar_math_expression_new_constant ( FoobarMathConstant constant ); +FoobarMathExpression* foobar_math_expression_new_operation( FoobarMathOperation operation, + FoobarMathExpression* lhs, + FoobarMathExpression* rhs ); +void foobar_math_expression_print ( FoobarMathExpression const* expr, + gint indentation ); +void foobar_math_expression_free ( FoobarMathExpression* expression ); +void foobar_math_value_new_int ( FoobarMathValue* out_value ); +gboolean foobar_math_value_from_string ( gchar const* input, + gsize input_length, + FoobarMathValue* out_value ); +void foobar_math_value_from_float ( long double value, + FoobarMathValue* out_value ); +void foobar_math_value_copy ( FoobarMathValue value, + FoobarMathValue* out_value ); +void foobar_math_value_free ( FoobarMathValue value ); +void foobar_math_value_negate ( FoobarMathValue* value ); +gboolean foobar_math_value_add ( FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ); +gboolean foobar_math_value_sub ( FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ); +gboolean foobar_math_value_mul ( FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ); +gboolean foobar_math_value_div ( FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ); +gboolean foobar_math_value_pow ( FoobarMathValue lhs, + FoobarMathValue rhs, + FoobarMathValue* out_value ); +gboolean foobar_math_value_is_simple_int ( FoobarMathValue value ); +gchar* foobar_math_value_to_string ( FoobarMathValue value ); +long double foobar_math_value_to_float ( FoobarMathValue value ); +gboolean foobar_math_evaluate ( FoobarMathExpression const* expr, + FoobarMathValue* out_value ); G_END_DECLS -- cgit v1.3.1 From 83d650b82e5209d2ca24cc1e6bf04e0644b3f615 Mon Sep 17 00:00:00 2001 From: Hannes Schulze Date: Mon, 4 Nov 2024 12:51:05 +0100 Subject: add docs --- src/services/quick-answers/math-lexer.c | 73 ++++++ src/services/quick-answers/math-parser.c | 110 ++++++-- src/services/quick-answers/math.c | 437 ++++++++++++++++++++----------- src/services/quick-answers/math.h | 8 +- 4 files changed, 462 insertions(+), 166 deletions(-) (limited to 'src/services/quick-answers/math-parser.c') diff --git a/src/services/quick-answers/math-lexer.c b/src/services/quick-answers/math-lexer.c index b0d24b7..7fbe877 100644 --- a/src/services/quick-answers/math-lexer.c +++ b/src/services/quick-answers/math-lexer.c @@ -1,5 +1,24 @@ #include "services/quick-answers/math.h" +// +// FoobarMathToken: +// +// A token in a mathematical expression. The token contents are left as-is and need not be null-terminated. For example, +// "sin(pi) - 3" would be represented as: +// - IDENTIFIER: "sin" +// - PAREN_OPEN: "(" +// - IDENTIFIER: "pi" +// - PAREN_CLOSE: ")" +// - MINUS: "-" +// - NUMBER: "3" +// + +// +// Lexer: +// +// The lexer context/state which is passed around. +// + typedef struct _Lexer Lexer; struct _Lexer @@ -24,6 +43,18 @@ static void lexer_commit_token ( Lexer* ctx, static void lexer_commit_single( Lexer* ctx, FoobarMathTokenType type ); +// --------------------------------------------------------------------------------------------------------------------- +// Lexing +// --------------------------------------------------------------------------------------------------------------------- + +// +// Divide an input string into a list of tokens. +// +// On success, this will return a newly allocated array of tokens which should be freed using g_free. The number of +// elements will be written into out_count. +// +// On error, this will return NULL. +// FoobarMathToken* foobar_math_lex( gchar const* input, gsize input_length, @@ -115,16 +146,29 @@ FoobarMathToken* foobar_math_lex( return g_array_steal( result, out_count ); } +// --------------------------------------------------------------------------------------------------------------------- +// Character Classification +// --------------------------------------------------------------------------------------------------------------------- + +// +// Check if a character is a whitespace symbol (space, tab, carriage return). +// gboolean char_is_whitespace( char c ) { return c == ' ' || c == '\t' || c == '\r'; } +// +// Check if a character is a decimal digit. +// gboolean char_is_digit( char c ) { return c >= '0' && c <= '9'; } +// +// Check if a character belongs to an identifier (like "sin", "pi", etc.). +// gboolean char_is_identifier( char c ) { // Identifiers are all lowercase ASCII. @@ -132,6 +176,15 @@ gboolean char_is_identifier( char c ) return c >= 'a' && c <= 'z'; } +// --------------------------------------------------------------------------------------------------------------------- +// State Helpers +// --------------------------------------------------------------------------------------------------------------------- + +// +// Peek at the current character without consuming it. +// +// If this is the end of the input string, return 0. +// char lexer_peek( Lexer const* ctx, gsize offset ) @@ -142,6 +195,11 @@ char lexer_peek( return ctx->input[position]; } +// +// Consume the current character, moving forward to the next one. +// +// If this is the end of the input string, return 0. +// char lexer_pop( Lexer* ctx ) { if ( ctx->position >= ctx->input_length ) { return 0; } @@ -149,11 +207,21 @@ char lexer_pop( Lexer* ctx ) return ctx->input[ctx->position++]; } +// +// Start recording a token by remembering the current position. +// +// The current character will be the first one in the token. +// void lexer_begin_token( Lexer* ctx ) { ctx->token_start = ctx->position; } +// +// Stop recording a token, saving the string between the call to lexer_begin_token as the specified type. +// +// The current character will not be a part of the token. +// void lexer_commit_token( Lexer* ctx, FoobarMathTokenType type ) @@ -165,6 +233,11 @@ void lexer_commit_token( g_array_append_val( ctx->result, token ); } +// +// Consume the current character and record it as a token. +// +// This is equivalent to calling lexer_begin_token, lexer_pop, and lexer_commit_token. +// void lexer_commit_single( Lexer* ctx, FoobarMathTokenType type ) diff --git a/src/services/quick-answers/math-parser.c b/src/services/quick-answers/math-parser.c index 7f93552..17d976d 100644 --- a/src/services/quick-answers/math-parser.c +++ b/src/services/quick-answers/math-parser.c @@ -1,5 +1,11 @@ #include "services/quick-answers/math.h" +// +// Parser: +// +// The parser context/state which is passed around. +// + typedef struct _Parser Parser; struct _Parser @@ -9,6 +15,12 @@ struct _Parser gsize position; }; +// +// InfixPrecedence: +// +// Value indicating how strongly infix operators should bind. The higher the value, the stronger they should bind. +// + typedef enum { INFIX_PRECEDENCE_INVALID = -1, @@ -18,8 +30,6 @@ typedef enum INFIX_PRECEDENCE_EXPONENTS = 3, } InfixPrecedence; -static FoobarMathToken const* parser_peek ( Parser const* ctx ); -static FoobarMathToken const* parser_pop ( Parser* ctx ); static FoobarMathExpression* parser_process ( Parser* ctx, FoobarMathExpression* lhs, InfixPrecedence min_precedence ); @@ -31,11 +41,24 @@ static FoobarMathExpression* parser_process_function ( Parser* FoobarMathFunction function ); static FoobarMathExpression* parser_process_parens ( Parser* ctx ); static FoobarMathExpression* parser_process_sign ( Parser* ctx ); +static FoobarMathToken const* parser_peek ( Parser const* ctx ); +static FoobarMathToken const* parser_pop ( Parser* ctx ); static gboolean parser_match_identifier ( FoobarMathToken const* token, gchar const* identifier ); static InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ); static FoobarMathOperation parser_operator ( FoobarMathToken const* token ); +// --------------------------------------------------------------------------------------------------------------------- +// Parsing +// --------------------------------------------------------------------------------------------------------------------- + +// +// Transform a sequence of tokens into a mathematical expression. +// +// On success, this will return a newly allocated expression which should be freed using foobar_math_expression_free. +// +// On error, this will return NULL. +// FoobarMathExpression* foobar_math_parse( FoobarMathToken const* tokens, gsize tokens_count ) @@ -59,20 +82,9 @@ FoobarMathExpression* foobar_math_parse( return expr; } -FoobarMathToken const* parser_peek( Parser const* ctx ) -{ - if ( ctx->position >= ctx->tokens_count ) { return NULL; } - - return &ctx->tokens[ctx->position]; -} - -FoobarMathToken const* parser_pop( Parser* ctx ) -{ - if ( ctx->position >= ctx->tokens_count ) { return NULL; } - - return &ctx->tokens[ctx->position++]; -} - +// +// Process tokens until the end of the current precedence scope (indicated by min_precedence), starting at an operator. +// FoobarMathExpression* parser_process( Parser* ctx, FoobarMathExpression* lhs, @@ -113,6 +125,12 @@ FoobarMathExpression* parser_process( return lhs; } +// +// Process a single value which may be either a constant, function, number, expression enclosed in parenthesis or +// negation. +// +// If an unexpected token is encountered (i.e. an operator), this will return FALSE. +// FoobarMathExpression* parser_process_single( Parser* ctx, gboolean allow_sign ) @@ -143,6 +161,11 @@ FoobarMathExpression* parser_process_single( } } +// +// Parse an identifier. +// +// If the identifier is a function, this will expected parenthesis and an expression afterwards. +// FoobarMathExpression* parser_process_identifier( Parser* ctx ) { FoobarMathToken const* token = parser_pop( ctx ); @@ -216,6 +239,9 @@ FoobarMathExpression* parser_process_identifier( Parser* ctx ) } } +// +// Process a numeric value. +// FoobarMathExpression* parser_process_number( Parser* ctx ) { FoobarMathToken const* token = parser_pop( ctx ); @@ -228,6 +254,9 @@ FoobarMathExpression* parser_process_number( Parser* ctx ) return foobar_math_expression_new_value( value ); } +// +// Process a function's parameter which should be enclosed in parenthesis. +// FoobarMathExpression* parser_process_function( Parser* ctx, FoobarMathFunction function ) @@ -244,6 +273,9 @@ FoobarMathExpression* parser_process_function( return foobar_math_expression_new_function( function, arg ); } +// +// Process an expression enclosed in parenthesis. +// FoobarMathExpression* parser_process_parens( Parser* ctx ) { parser_pop( ctx ); @@ -260,6 +292,9 @@ FoobarMathExpression* parser_process_parens( Parser* ctx ) return result; } +// +// Process a sign (- or +) which may be used for negation of an expression. +// FoobarMathExpression* parser_process_sign( Parser* ctx ) { FoobarMathToken const* token = parser_pop( ctx ); @@ -276,6 +311,43 @@ FoobarMathExpression* parser_process_sign( Parser* ctx ) } } +// --------------------------------------------------------------------------------------------------------------------- +// State Helpers +// --------------------------------------------------------------------------------------------------------------------- + +// +// Peek at the current token without consuming it. +// +// If this is the end of the token list, return NULL. +// +FoobarMathToken const* parser_peek( Parser const* ctx ) +{ + if ( ctx->position >= ctx->tokens_count ) { return NULL; } + + return &ctx->tokens[ctx->position]; +} + +// +// Consume the current token. +// +// If this is the end of the token list, return NULL. +// +FoobarMathToken const* parser_pop( Parser* ctx ) +{ + if ( ctx->position >= ctx->tokens_count ) { return NULL; } + + return &ctx->tokens[ctx->position++]; +} + +// --------------------------------------------------------------------------------------------------------------------- +// Helpers +// --------------------------------------------------------------------------------------------------------------------- + +// +// Match a token's string against the given identifier string. +// +// This is necessary because the token's content is not a null-terminated string. +// gboolean parser_match_identifier( FoobarMathToken const* token, gchar const* identifier ) @@ -285,6 +357,9 @@ gboolean parser_match_identifier( return !strncmp( token->data, identifier, token->length ); } +// +// Get the precedence of an infix operator token or INVALID. +// InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ) { if ( token ) @@ -311,6 +386,9 @@ InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ) return INFIX_PRECEDENCE_INVALID; } +// +// Get the operation for an infix operator token. This requires the token to be valid. +// FoobarMathOperation parser_operator( FoobarMathToken const* token ) { switch ( token->type ) diff --git a/src/services/quick-answers/math.c b/src/services/quick-answers/math.c index e813808..69219e2 100644 --- a/src/services/quick-answers/math.c +++ b/src/services/quick-answers/math.c @@ -3,6 +3,16 @@ #include "services/quick-answers/math.h" #include +// +// FoobarMathExpression: +// +// A fully parsed mathematical expression which can be evaluated, for example "sin(pi) - 3" would be represented as: +// - Operation: SUB +// - Function: SIN +// - Constant: PI +// - Value: 3 +// + struct _FoobarMathExpression { FoobarMathExpressionType type; @@ -34,6 +44,29 @@ struct _FoobarMathExpression }; }; +// +// FoobarMathValue: +// +// Representation of a value. The goal of this memory structure is to store the value as an integer for as long as +// possible. Because of this, there is a "decimal_places" field, so the actual value of an integer is +// $v * 10^(-decimal_places)$. +// +// If absolutely necessary (for example, because we use a function like sin), the value is converted to a floating-point +// value. +// +// Note that we use GMP to store the integer value to allow for arbitrarily large values. Because of this, the structure +// should always be freed using foobar_math_value_free. +// + +// --------------------------------------------------------------------------------------------------------------------- +// Expressions +// --------------------------------------------------------------------------------------------------------------------- + +// +// Helper to allocate a new FoobarMathExpression representing a value. +// +// Ownership of "value" is transferred to the new expression. +// FoobarMathExpression* foobar_math_expression_new_value( FoobarMathValue value ) { FoobarMathExpression* res = g_new0( FoobarMathExpression, 1 ); @@ -42,6 +75,12 @@ FoobarMathExpression* foobar_math_expression_new_value( FoobarMathValue value ) return res; } +// +// Helper to allocate a new FoobarMathExpression representing a function to be evaluated with another expression as its +// parameter. +// +// Ownership of "input" is transferred to the new expression. +// FoobarMathExpression* foobar_math_expression_new_function( FoobarMathFunction function, FoobarMathExpression* input ) @@ -53,6 +92,9 @@ FoobarMathExpression* foobar_math_expression_new_function( return res; } +// +// Helper to allocate a new FoobarMathExpression representing a known constant. +// FoobarMathExpression* foobar_math_expression_new_constant( FoobarMathConstant constant ) { FoobarMathExpression* res = g_new0( FoobarMathExpression, 1 ); @@ -61,6 +103,12 @@ FoobarMathExpression* foobar_math_expression_new_constant( FoobarMathConstant co return res; } +// +// Helper to allocate a new FoobarMathExpression representing an operation to be evaluated with two expressions as its +// parameters. +// +// Ownership of "lhs" and "rhs" is transferred to the new expression. +// FoobarMathExpression* foobar_math_expression_new_operation( FoobarMathOperation operation, FoobarMathExpression* lhs, @@ -74,6 +122,9 @@ FoobarMathExpression* foobar_math_expression_new_operation( return res; } +// +// Release the memory associated with a mathematical expression, along with the expressions it owns. +// void foobar_math_expression_free( FoobarMathExpression* expression ) { if ( expression ) @@ -101,6 +152,12 @@ void foobar_math_expression_free( FoobarMathExpression* expression ) } } +// +// Print a tree representation of a mathematical expression. +// +// This is mainly useful for debugging. "indentation" describes the current indentation level for the recursive call +// (should be 0 initially). +// void foobar_math_expression_print( FoobarMathExpression const* expr, gint indentation ) @@ -213,6 +270,158 @@ void foobar_math_expression_print( } } +// +// Evaluate an expression, producing a value. +// +// On success (indicated by the return value TRUE), the value should be freed using foobar_math_value_free. +// +gboolean foobar_math_evaluate( + FoobarMathExpression const* expr, + FoobarMathValue* out_value ) +{ + switch ( expr->type ) + { + case FOOBAR_MATH_EXPRESSION_VALUE: + foobar_math_value_copy( expr->value.v, out_value ); + return TRUE; + case FOOBAR_MATH_EXPRESSION_CONSTANT: + switch ( expr->constant.c ) + { + case FOOBAR_MATH_CONSTANT_PI: + foobar_math_value_from_float( M_PIl, out_value ); + return TRUE; + case FOOBAR_MATH_CONSTANT_E: + foobar_math_value_from_float( M_El, out_value ); + return TRUE; + default: + g_warn_if_reached( ); + return FALSE; + } + case FOOBAR_MATH_EXPRESSION_FUNCTION: + { + FoobarMathValue input = { 0 }; + if ( !foobar_math_evaluate( expr->function.input, &input ) ) { return FALSE; } + + if ( expr->function.f == FOOBAR_MATH_FUNCTION_NEGATE ) + { + *out_value = input; + foobar_math_value_negate( out_value ); + return TRUE; + } + + long double input_float = foobar_math_value_to_float( input ); + foobar_math_value_free( input ); + + long double result = NAN; + switch ( expr->function.f ) + { + case FOOBAR_MATH_FUNCTION_SIN: + result = sinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_COS: + result = cosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_SEC: + result = 1.L / cosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_CSC: + result = 1.L / sinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_TAN: + result = tanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_COT: + result = 1.L / tanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCSIN: + result = asinl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCOS: + result = acosl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCSEC: + result = acosl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCSC: + result = asinl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCTAN: + result = atanl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_ARCCOT: + result = atanl( 1.L / input_float ); + break; + case FOOBAR_MATH_FUNCTION_EXP: + result = expl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_SQRT: + result = sqrtl( input_float ); + break; + case FOOBAR_MATH_FUNCTION_NEGATE: + default: + g_warn_if_reached( ); + return FALSE; + } + + if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } + + foobar_math_value_from_float( result, out_value ); + return TRUE; + } + case FOOBAR_MATH_EXPRESSION_OPERATION: + { + FoobarMathValue lhs = { 0 }; + if ( !foobar_math_evaluate( expr->operation.lhs, &lhs ) ) { return FALSE; } + FoobarMathValue rhs = { 0 }; + if ( !foobar_math_evaluate( expr->operation.rhs, &rhs ) ) + { + foobar_math_value_free( lhs ); + return FALSE; + } + + gboolean success = FALSE; + switch ( expr->operation.o ) + { + case FOOBAR_MATH_OPERATION_ADD: + success = foobar_math_value_add( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_SUB: + success = foobar_math_value_sub( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_MUL: + success = foobar_math_value_mul( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_DIV: + success = foobar_math_value_div( &lhs, &rhs, out_value ); + break; + case FOOBAR_MATH_OPERATION_POW: + success = foobar_math_value_pow( &lhs, &rhs, out_value ); + break; + default: + g_warn_if_reached( ); + break; + } + + foobar_math_value_free( lhs ); + foobar_math_value_free( rhs ); + + return success; + } + default: + g_warn_if_reached( ); + return FALSE; + } +} + +// --------------------------------------------------------------------------------------------------------------------- +// Values +// --------------------------------------------------------------------------------------------------------------------- + +// +// Initialize a new integer value to zero. +// +// After this, the structure should be freed using foobar_math_value_free. +// void foobar_math_value_new_int( FoobarMathValue* out_value ) { out_value->type = FOOBAR_MATH_VALUE_INT; @@ -220,6 +429,24 @@ void foobar_math_value_new_int( FoobarMathValue* out_value ) out_value->int_value.decimal_places = 0; } +// +// Initialize a new value from its floating point representation. +// +// Although technically not necessary, you should still call foobar_math_value_free on the returned value. +// +void foobar_math_value_from_float( + long double value, + FoobarMathValue* out_value ) +{ + out_value->type = FOOBAR_MATH_VALUE_FLOAT; + out_value->float_value.v = value; +} + +// +// Parse a value from its string representation. This will always return an integer representation. +// +// On success (return value TRUE), the structure should be freed using foobar_math_value_free. +// gboolean foobar_math_value_from_string( gchar const* input, gsize input_length, @@ -251,14 +478,11 @@ gboolean foobar_math_value_from_string( return TRUE; } -void foobar_math_value_from_float( - long double value, - FoobarMathValue* out_value ) -{ - out_value->type = FOOBAR_MATH_VALUE_FLOAT; - out_value->float_value.v = value; -} - +// +// Create a copy of a value, allocating necessary memory. +// +// After this, the structure should be freed using foobar_math_value_free. +// void foobar_math_value_copy( FoobarMathValue value, FoobarMathValue* out_value ) @@ -278,6 +502,11 @@ void foobar_math_value_copy( } } +// +// Release memory associated with a value. +// +// This is necessary because the integer representation is stored using GMP, which can store arbitrarily large values. +// void foobar_math_value_free( FoobarMathValue value ) { switch ( value.type ) @@ -293,6 +522,13 @@ void foobar_math_value_free( FoobarMathValue value ) } } +// --------------------------------------------------------------------------------------------------------------------- +// Operations +// --------------------------------------------------------------------------------------------------------------------- + +// +// Operation equivalent to "value *= -1". +// void foobar_math_value_negate( FoobarMathValue* value ) { switch ( value->type ) @@ -309,6 +545,11 @@ void foobar_math_value_negate( FoobarMathValue* value ) } } +// +// Operation setting "out_value = lhs + rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_add( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -328,6 +569,11 @@ gboolean foobar_math_value_add( return TRUE; } +// +// Operation setting "out_value = lhs - rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_sub( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -347,6 +593,11 @@ gboolean foobar_math_value_sub( return TRUE; } +// +// Operation setting "out_value = lhs * rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_mul( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -366,6 +617,11 @@ gboolean foobar_math_value_mul( return TRUE; } +// +// Operation setting "out_value = lhs / rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_div( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -400,6 +656,11 @@ gboolean foobar_math_value_div( return TRUE; } +// +// Operation setting "out_value = lhs ^ rhs". +// +// After this, the result value should be freed using foobar_math_value_free. +// gboolean foobar_math_value_pow( FoobarMathValue* lhs, FoobarMathValue* rhs, @@ -425,6 +686,14 @@ gboolean foobar_math_value_pow( return TRUE; } +// +// Ensure that two integer values have the same number of decimal places. +// +// This may change the in-memory-representation of a value, but not its actual value. It only increases the precision of +// one value +// +// If either a or b is not stored as an integer, this will return FALSE. +// gboolean foobar_math_value_unify_integers( FoobarMathValue* a, FoobarMathValue* b ) @@ -457,6 +726,15 @@ gboolean foobar_math_value_unify_integers( return TRUE; } +// --------------------------------------------------------------------------------------------------------------------- +// Conversions +// --------------------------------------------------------------------------------------------------------------------- + +// +// Format a value as a string. +// +// The result is a null-terminated string which should be freed using g_free. +// gchar* foobar_math_value_to_string( FoobarMathValue value ) { switch ( value.type ) @@ -538,6 +816,11 @@ gchar* foobar_math_value_to_string( FoobarMathValue value ) } } +// +// Convert a value to its floating-point representation. +// +// This may be a lossy conversion and should only be done if absolutely necessary. +// long double foobar_math_value_to_float( FoobarMathValue value ) { switch ( value.type ) @@ -566,141 +849,3 @@ long double foobar_math_value_to_float( FoobarMathValue value ) return 0; } } - -gboolean foobar_math_evaluate( - FoobarMathExpression const* expr, - FoobarMathValue* out_value ) -{ - switch ( expr->type ) - { - case FOOBAR_MATH_EXPRESSION_VALUE: - foobar_math_value_copy( expr->value.v, out_value ); - return TRUE; - case FOOBAR_MATH_EXPRESSION_CONSTANT: - switch ( expr->constant.c ) - { - case FOOBAR_MATH_CONSTANT_PI: - foobar_math_value_from_float( M_PIl, out_value ); - return TRUE; - case FOOBAR_MATH_CONSTANT_E: - foobar_math_value_from_float( M_El, out_value ); - return TRUE; - default: - g_warn_if_reached( ); - return FALSE; - } - case FOOBAR_MATH_EXPRESSION_FUNCTION: - { - FoobarMathValue input = { 0 }; - if ( !foobar_math_evaluate( expr->function.input, &input ) ) { return FALSE; } - - if ( expr->function.f == FOOBAR_MATH_FUNCTION_NEGATE ) - { - *out_value = input; - foobar_math_value_negate( out_value ); - return TRUE; - } - - long double input_float = foobar_math_value_to_float( input ); - foobar_math_value_free( input ); - - long double result = NAN; - switch ( expr->function.f ) - { - case FOOBAR_MATH_FUNCTION_SIN: - result = sinl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_COS: - result = cosl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_SEC: - result = 1.L / cosl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_CSC: - result = 1.L / sinl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_TAN: - result = tanl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_COT: - result = 1.L / tanl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCSIN: - result = asinl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCCOS: - result = acosl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCSEC: - result = acosl( 1.L / input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCCSC: - result = asinl( 1.L / input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCTAN: - result = atanl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_ARCCOT: - result = atanl( 1.L / input_float ); - break; - case FOOBAR_MATH_FUNCTION_EXP: - result = expl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_SQRT: - result = sqrtl( input_float ); - break; - case FOOBAR_MATH_FUNCTION_NEGATE: - default: - g_warn_if_reached( ); - return FALSE; - } - - if ( isnanl( result ) || isinfl( result ) ) { return FALSE; } - - foobar_math_value_from_float( result, out_value ); - return TRUE; - } - case FOOBAR_MATH_EXPRESSION_OPERATION: - { - FoobarMathValue lhs = { 0 }; - if ( !foobar_math_evaluate( expr->operation.lhs, &lhs ) ) { return FALSE; } - FoobarMathValue rhs = { 0 }; - if ( !foobar_math_evaluate( expr->operation.rhs, &rhs ) ) - { - foobar_math_value_free( lhs ); - return FALSE; - } - - gboolean success = FALSE; - switch ( expr->operation.o ) - { - case FOOBAR_MATH_OPERATION_ADD: - success = foobar_math_value_add( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_SUB: - success = foobar_math_value_sub( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_MUL: - success = foobar_math_value_mul( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_DIV: - success = foobar_math_value_div( &lhs, &rhs, out_value ); - break; - case FOOBAR_MATH_OPERATION_POW: - success = foobar_math_value_pow( &lhs, &rhs, out_value ); - break; - default: - g_warn_if_reached( ); - break; - } - - foobar_math_value_free( lhs ); - foobar_math_value_free( rhs ); - - return success; - } - default: - g_warn_if_reached( ); - return FALSE; - } -} diff --git a/src/services/quick-answers/math.h b/src/services/quick-answers/math.h index c66a2bf..fafa73d 100644 --- a/src/services/quick-answers/math.h +++ b/src/services/quick-answers/math.h @@ -112,13 +112,15 @@ FoobarMathExpression* foobar_math_expression_new_operation( FoobarMathOperation FoobarMathExpression* rhs ); void foobar_math_expression_print ( FoobarMathExpression const* expr, gint indentation ); +gboolean foobar_math_evaluate ( FoobarMathExpression const* expr, + FoobarMathValue* out_value ); void foobar_math_expression_free ( FoobarMathExpression* expression ); void foobar_math_value_new_int ( FoobarMathValue* out_value ); +void foobar_math_value_from_float ( long double value, + FoobarMathValue* out_value ); gboolean foobar_math_value_from_string ( gchar const* input, gsize input_length, FoobarMathValue* out_value ); -void foobar_math_value_from_float ( long double value, - FoobarMathValue* out_value ); void foobar_math_value_copy ( FoobarMathValue value, FoobarMathValue* out_value ); void foobar_math_value_free ( FoobarMathValue value ); @@ -142,7 +144,5 @@ gboolean foobar_math_value_unify_integers ( FoobarMathValue* FoobarMathValue* b ); gchar* foobar_math_value_to_string ( FoobarMathValue value ); long double foobar_math_value_to_float ( FoobarMathValue value ); -gboolean foobar_math_evaluate ( FoobarMathExpression const* expr, - FoobarMathValue* out_value ); G_END_DECLS -- cgit v1.3.1