calculator.c

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

#include <math.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../../young/youngc.h"

#define  TRIM  2
#define  PRIORITY  4

const char cleans[TRIM] = { ' ', '\t' };
const char* operators[PRIORITY] = { "^", "*/%", "+-", "()" };

/* 判断运算符的优先级 */
int OperPriority( char oper )
{
    int i;
    for( i = 0; i < PRIORITY; ++i )
    {
        if( strchr( operators[i], oper ) )
            return i + 1;
    }
    return 0;
}

/* 转换成逆波兰表达式，并返回数字的个数 */
int transfer( ncstring* expr, chkarray* exprdeq )
{
    int result = 0;
    char *s = ncstr_begin( expr );
    size_t i, numlen, len = ncstr_size( expr );
    ncstring symbol;
    chkarray operstack;

    ncstr_init( &symbol );
    chkarr_init( &operstack, sizeof(char), 0, NULL, NULL, NULL, NULL, NULL,
                 NULL, pool_alloc, pool_free );

    for( i = 1; len >= i; ++i,++s )
    {
        if( isspace(*s) )  /* 空格 */
            continue;
        if( isdigit(*s) || '.' == *s )  /* 数字 */
            ncstr_push_back( &symbol, *s );
        else if( '-' == *s && ncstr_size(&symbol) == 0
                 && (i == 1 || *(s - 1) != ')') ) /* 负号 */
            ncstr_push_back( &symbol, *s );
        else  /* 运算符 */
        {
            numlen = ncstr_size( &symbol );
            if( numlen > 0 )  /* 先把数字压进队列 */
            {
                chkarr_push_back( exprdeq, &symbol );
                ncstr_erase_range( &symbol, 0, SIZE_MAX );
                ++result;
            }

            if( true == chkarr_empty(&operstack) )
            {
                if( OperPriority( *s ) > 0 )  /* 必须是可以识别的运算符 */
                    chkarr_push_back( &operstack, s );  /* 将运算符压进栈 */
                else
                {
                    result = -1;
                    goto EXITTRANS;
                }
            }
            else if( '(' == *s )  /* 左括号 */
                chkarr_push_back( &operstack, s );
            else if( ')' == *s )  /* 右括号 */
            {
                /* 把'('之后的运算符全部从栈中弹出并压进队列 */
                while( '(' != CHKARRAY_BACK(operstack, char) )
                {
                    ncstr_push_back( &symbol, CHKARRAY_BACK(operstack, char) );
                    chkarr_push_back( exprdeq, &symbol );
                    ncstr_erase_range( &symbol, 0, SIZE_MAX );
                    chkarr_pop_back( &operstack );
                }
                chkarr_pop_back( &operstack );  /* 弹出'(' */
            }
            else  /* 其他运算符 */
            {
                int oldprio, newprio = OperPriority( *s );
                if( newprio <= 0 )
                {
                    result = -1;
                    goto EXITTRANS;
                }
                oldprio = OperPriority( CHKARRAY_BACK(operstack, char) );
                if( newprio < oldprio )  /* 新的运算符优先级更高 */
                    chkarr_push_back( &operstack, s );
                else
                {
                    ncstr_push_back( &symbol, CHKARRAY_BACK(operstack, char) );
                    chkarr_push_back( exprdeq, &symbol );
                    ncstr_erase_range( &symbol, 0, SIZE_MAX );
                    CHKARRAY_BACK(operstack, char) = *s;
                }
            }
        }
    }

    /* 如果还有数字，那么还要把数字压进栈 */
    numlen = ncstr_size( &symbol );
    if( numlen > 0 )
    {
        chkarr_push_back( exprdeq, &symbol );
        ncstr_erase_range( &symbol, 0, SIZE_MAX );
        ++result;
    }

    /* 把剩余的运算符依次弹出栈并压进队列 */
    for( len = chkarr_size(&operstack); len > 0; --len )
    {
        ncstr_push_back( &symbol, CHKARRAY_BACK(operstack, char) );
        chkarr_push_back( exprdeq, &symbol );
        ncstr_erase_range( &symbol, 0, SIZE_MAX );
        chkarr_pop_back( &operstack );
    }

EXITTRANS:
    chkarr_destroy( &operstack );
    ncstr_destroy( &symbol );
    return result;
}

double calculate( double left, double right, char oper )
{
    double result = 0.0;

    switch( oper )
    {
        case '+':
            result = left + right;
            break;
        case '-':
            result = left - right;
            break;
        case '*':
            result = left * right;
            break;
        case '/':
            if( right != 0.0 )
                result = left / right;
            else
                printf( "\n<<< error: zero divisor!\n" );
            break;
        case '%':
            result = (long)left % (long)right;
            break;
        case '^':
            result = pow( left, right );
            break;
        default:
            printf( "\n<<< error: unknown operator %c!\n", oper );
            break;
    }

    return result;
}

int main( int argc, char* argv[] )
{
    size_t i = 0, len = 0, numcount = 0;
    double val = 0.0;
    ncstring input, *pstr;
    chkarray valdeq, exprdeq;

    ncstr_init( &input );
    chkarr_init( &valdeq, sizeof(double), 0, NULL, NULL, NULL,
                 NULL, NULL, NULL, pool_alloc, pool_free );
    chkarr_init( &exprdeq, sizeof(ncstring), 0, (ylib_fp_oper_t)ncstr_init,
                 (ylib_fp_copy_t)ncstr_init_copy, (ylib_fp_copy_t)ncstr_assign_copy,
                 (ylib_fp_move_t)ncstr_init_move, (ylib_fp_move_t)ncstr_assign_move,
                 (ylib_fp_oper_t)ncstr_destroy, pool_alloc, pool_free );

    for(;;)
    {
        printf( "please input an expression, no input to exit:\n>>> " );

        ncstr_erase_range( &input, 0, SIZE_MAX );
        ncstr_getline( &input, '\n' );
        if( ncstr_size(&input) == 0 )
            goto EXITMAIN;

        ncstr_trim( &input, 0, cleans, TRIM );
        numcount = transfer( &input, &exprdeq );
        if( numcount < 0 )
        {
            printf( "<<< expression error!\n" );
            continue;
        }

        /* 输出转换后的逆波兰表达式 */
/*        len = chkarr_size( &exprdeq );
        printf( "<<< reverse Polish notation: " );
        for( i = 0; i < len; ++i )
            printf( "%s ", ncstr_to_string( (ncstring*)chkarr_index(&exprdeq, i) ) );
        putchar( '\n' );
*/
        i = 0;
        while( !chkarr_empty(&exprdeq) )
        {
            pstr = &CHKARRAY_FRONT( exprdeq, ncstring );
            if( ncstr_size(pstr) == 1 && !isdigit(*ncstr_begin(pstr)) )  /* 运算符 */
            {
                if( i > numcount )
                {
                    val = calculate( *((double*)chkarr_index(&valdeq, 0)),
                                     *((double*)chkarr_index(&valdeq, 1)),
                                     *ncstr_begin(pstr) );
                    chkarr_pop_front( &valdeq );
                    chkarr_pop_front( &valdeq );
                    chkarr_push_front( &valdeq, &val );
                }
                else
                {
                    len = chkarr_size( &valdeq );
                    val = calculate( *((double*)chkarr_index(&valdeq, len - 2)),
                                     *((double*)chkarr_index(&valdeq, len - 1)),
                                     *ncstr_begin(pstr) );
                    chkarr_pop_back( &valdeq );
                    chkarr_pop_back( &valdeq );
                    chkarr_push_back( &valdeq, &val );
                    if( i == numcount )
                        ++i;
                }
            }
            else  /* 数字 */
            {
                val = atof( ncstr_to_string(pstr) );
                chkarr_push_back( &valdeq, &val );
                ++i;
            }
            chkarr_pop_front( &exprdeq );
        }

        printf( "<<< %s = %f\n", ncstr_to_string(&input),
                CHKARRAY_FRONT( valdeq, double ) );
        chkarr_erase_range( &valdeq, 0, chkarr_size(&valdeq) );
    }

EXITMAIN:
    chkarr_destroy( &exprdeq );
    chkarr_destroy( &valdeq );
    ncstr_destroy( &input );
    return 0;
}