Тестовое задание

calc.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>

/* ----------------------------------------------------------------------------
 * Напишите программу, которая считывает со стандартного ввода строку и выводит
 * на стандартный вывод значение арифметического выражения, содержащегося в
 * этой строке.
 *
 * Арифметическое выражение содержит целые константы, знаки 4-х арифметических
 * действий (+,-,*,/) и скобки.
 *
 * # Дополнил '%' (остаток от деления) и '**' (возведение в степень)
 * # В решении используется преобразование выражения в обратную польскую
 * нотацию с последующим разбором получившегося.
 * # Со стеками городить на стал, хотя есть немало хороших решений на C,
 * включая моё собственное, см. в гитхабе :)
 * # Со строками аналогично, всё вручную.
 * # Все токены, включая числа, хранятся в виде строк. Не самое гуманное
 * решение, но оно же и облегчение в отладке, и задел на будущее (а если
 * захочется прикрутить блэкджек и функции, например?)
 * # Диагностика примитивная, да.
 * # И унарных операторов оно не понимает (то есть такого: -1, +2, -(3**4)...)
 * # Зато приоритеты операций - понимает.
 * # Ну и вообще.
 -----------------------------------------------------------------------------*/
#define TOKEN_MAX_LENGTH    32
#define STACK_SIZE          64

/* -------------------------------------------------------------------------- */
/* Стек операторов: */
static char op_stack[STACK_SIZE][TOKEN_MAX_LENGTH];
static size_t in_op_stack = 0;
/* Стек операндов и действий над ними: */
static char tok_stack[STACK_SIZE][TOKEN_MAX_LENGTH];
static size_t in_tok_stack = 0;

/* -------------------------------------------------------------------------- */
static void *fatal( const char *msg )
{
    fprintf( stderr, "%s!\n", msg );
    exit( EXIT_FAILURE );
    /* штоб было */
    return NULL;
}

/* -------------------------------------------------------------------------- */
static const char *op_pop()
{
    if( in_op_stack > 0 ) {
        in_op_stack--;
        return op_stack[in_op_stack];
    }

    /*
     * При правильно составленном исходном выражении извлечение из стека
     * операторов не может происходить при пустом стеке. Если попали сюда,
     * то что-то неправильно, например, дисбаланс открывающих и закрывающих
     * скобок.
     */
    return fatal( "op_pop() : op_stack is empty" );
}

/* -------------------------------------------------------------------------- */
static void _push( const char *val, char stack[][TOKEN_MAX_LENGTH], size_t *in,
                   const char *prefix )
{
    if( strlen( val ) >= TOKEN_MAX_LENGTH ) {
        fprintf( stderr, "%s_push() : token '%s' is too long!\n", prefix, val );
        exit( EXIT_FAILURE );
    }

    if( *in < STACK_SIZE ) {
        strcpy( stack[*in], val );
        ( *in )++;
    }
    else {
        fprintf( stderr, "%s_push('%s') : %s_stack is full!\n", prefix, val, prefix );
        exit( EXIT_FAILURE );
    }
}

/* -------------------------------------------------------------------------- */
static void op_push( const char *val )
{
    _push( val, op_stack, &in_op_stack, "op" );
}

/* -------------------------------------------------------------------------- */
static void t_push( const char *val )
{
    _push( val, tok_stack, &in_tok_stack, "tok" );
}

/* -------------------------------------------------------------------------- */
static int op_priority( const char *op )
{
    if( !strcmp( op, "+" ) || !strcmp( op, "-" ) ) {
        return 1;
    }

    if( !strcmp( op, "%" ) ) {
        return 2;
    }

    if( !strcmp( op, "*" ) || !strcmp( op, "/" ) ) {
        return 3;
    }

    if( !strcmp( op, "**" ) ) {
        return 4;
    }

    return 0;
}

/* ----------------------------------------------------------------------------
 * Чтобы обойтись без -lm. Переполнение отслеживается.
 --------------------------------------------------------------------------- */
static long lpow( long a, long b )
{
    long long rc = 1;

    if( b == 0 ) {
        return 1;
    }

    /*
     * Не будем высчитывать отрицательные степени
     */
    if( b < 0 ) {
        return 0;
    }

    while( b-- ) {
        rc *= a;
    }

    if( rc > LONG_MAX || rc < LONG_MIN ) {
        fprintf( stderr, " Arithmetic overflow in lpow(%ld, %ld)\n", a, b );
        exit( EXIT_FAILURE );
    }

    return ( long ) rc;
}

/* -------------------------------------------------------------------------- */
static long op( const char *a, const char *b, const char *c )
{
    long la = atol( a ), lb = atol( b );

    if( !strcmp( c, "+" ) ) {
        return la + lb;
    }

    /* reverse order! */
    if( !strcmp( c, "-" ) ) {
        return lb - la;
    }

    /* reverse order! */
    if( !strcmp( c, "%" ) ) {
        return lb % la;
    }

    if( !strcmp( c, "*" ) ) {
        return la * lb;
    }

    /* reverse order! */
    if( !strcmp( c, "**" ) ) {
        return lpow( lb, la );
    }

    /* reverse order! */
    if( !strcmp( c, "/" ) ) {
        if( la == 0 ) {
            fprintf( stderr, "Divizion by zero in op(%s %s %s)\n", b, c, a );
            exit( EXIT_FAILURE );
        }

        return lb / la;
    }

    fprintf( stderr, "Invalid operation '%s'\n", c );
    exit( EXIT_FAILURE );
}

/* ----------------------------------------------------------------------------
 * Разбирает входную строку. При обнаружении валидного токена записывает его в
 * виде ASCIIZ-строки в переменную *token.
 * При некорректном вводе вызывает fatal() с соответствующей диагностикой.
 * При достижении конца строки возвращает NULL. Если токен найден - возвращает
 * указатель на следующий за ним символ в строке-источнике.
 --------------------------------------------------------------------------- */
static const char *next_token( const char *s, char *token )
{
    static const char *tokens[] = { "+", "-", "%", "**", "*", "/", "(", ")" };
    size_t i;

    while( isspace( *s ) ) {
        ++s;
    }

    if( !*s ) {
        return NULL;
    }

    if( isdigit( *s ) ) {
        char *end;
        long long rc = strtoll( s, &end, 10 );
        i = end - s;

        if( ( i > 0 && i < TOKEN_MAX_LENGTH ) && ( rc <= LONG_MAX &&
                rc >= LONG_MIN ) ) {
            memcpy( token, s, i );
            token[i] = 0;
            return s + i;
        }

        return fatal( "Invalid number in input string" );
    }

    for( i = 0; i < sizeof( tokens ) / sizeof( tokens[0] ); i++ ) {
        size_t len = strlen( tokens[i] );

        if( !memcmp( s, tokens[i], len ) ) {
            strcpy( token, tokens[i] );
            return s + len;
        }
    }

    return fatal( "Invalid input string" );
}

/* -------------------------------------------------------------------------- */
static long evaluate( const char *s )
{
    size_t i;
    char token[TOKEN_MAX_LENGTH];
    in_tok_stack = in_op_stack = 0;

    /* 1. Строим ОПН */
    while( *s ) {
        s = next_token( s, token );

        if( !s ) {
            break;
        }

        /* Числа сохраняем в стеке t_stack */
        if( isdigit( *token ) ) {
            t_push( token );
            continue;
        }

        /* Открывающую скобку сохраняем в стеке операций */
        if( !strcmp( token, "(" ) ) {
            op_push( token );
            continue;
        }

        /*
         * Закрывающая скобка. Переносим всё из стека операций
         * в стек t_stack, вплоть до открывающей скобки
         */
        if( !strcmp( token, ")" ) ) {
            const char *op = op_pop();

            while( strcmp( op, "(" ) ) {
                t_push( op );
                op = op_pop();
            }
        }
        else {
            /*
             * Оператор.
             */
            int priority = op_priority( token );

            /*
             * Пока в стеке операций есть операции с более высоким
             * приоритетом - извлекаем их и заносим в t_stack.
             */
            while( in_op_stack ) {
                const char *op = op_pop();

                if( op_priority( op ) > priority ) {
                    t_push( op );
                }
                else {
                    op_push( op );
                    break;
                }
            }

            op_push( token );
        }
    }

    /* 2. Добиваем в хвост t_stack оставшиеся операторы */
    while( in_op_stack ) {
        t_push( op_pop() );
    }

    /* 3. Понеслась! */
    for( i = 0; i < in_tok_stack; i++ ) {
        if( isdigit( *tok_stack[i] ) ) {
            op_push( tok_stack[i] );
        }
        else {
            const char *a = op_pop();
            const char *b = op_pop();
            char buf[TOKEN_MAX_LENGTH];
            sprintf( buf, "%ld", op( a, b, tok_stack[i] ) );
            op_push( buf );
        }
    }

    return atol( op_pop() );
}

/* -------------------------------------------------------------------------- */
static size_t test( const char *s, long expect )
{
    long rc = evaluate( s );

    if( rc != expect ) {
        printf( "%s, expect: %ld, got %ld\n", s, expect, rc );
        return 1;
    }

    return 0;
}
/* -------------------------------------------------------------------------- */
int main()
{
    char *line = NULL;
    size_t line_length = 0;
    long rc;
    size_t errors = 0;

    if( getline( &line, &line_length, stdin ) < 0 ) {
        fatal( "getline() falied" );
    }

    rc = evaluate( line );
    printf( "Got '%s', result: %ld\n\nAnd now - tests!\n\n", line, rc );
    free( line );
    /* ну а как же без тестов? */
    errors += test( "1+20", 21 );
    errors += test( "1 + 20", 21 );
    errors += test( "1+20+300", 321 );
    errors += test( "1+20+300+4000", 4321 );
    errors += test( "24%10", 4 );
    errors += test( "24/2", 12 );
    errors += test( "2**3", 8 );
    errors += test( "(1+20)", 21 );
    errors += test( "1+10*2", 21 );
    errors += test( "10*2+1", 21 );
    errors += test( "(1+20)*2", 42 );
    errors += test( "2*(1+20)", 42 );
    errors += test( "(1+2)*(3+4)", 21 );
    errors += test( "2*3+4*5", 26 );
    errors += test( "100+2*10+3", 123 );
    errors += test( "2**3", 8 );
    errors += test( "2**3*5+2", 42 );
    errors += test( "5*2**3+2", 42 );
    errors += test( "2+5*2**3", 42 );
    errors += test( "1+2**3*10", 81 );
    errors += test( "2**3+2*10", 28 );
    errors += test( "5 * 4 + 3 * 2 + 1", 27 );
    printf( "Errors: %zu\n", errors );
    return errors > 0;
}

/* -------------------------------------------------------------------------- */