calculator++.cpp

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

#include <math.h>
#include <ctype.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include "../../young/youngcpp.hpp"

#define  TRIM  2
#define  PRIORITY  4

typedef  youngcpp::string  string_t;
typedef  youngcpp::deque<double>  dbdeq_t;
typedef  youngcpp::deque<string_t>  strdeq_t;
typedef  std::stack< char, youngcpp::deque<char> >  chstk_t;

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

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

//转换成逆波兰表达式，并返回数字的个数
int transfer( const string_t& expr, strdeq_t& exprdeq )
{
    int result = 0;
    const char *s = expr.begin();
    size_t i, numlen, len = expr.size();
    string_t symbol;
    chstk_t operstack;

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

            if( operstack.empty() )
            {
                if( OperPriority( *s ) > 0 )  //必须是可以识别的运算符
                    operstack.push( *s );  //将运算符压进栈
                else
                    return -1;
            }
            else if( '(' == *s )  //左括号
                operstack.push( *s );
            else if( ')' == *s )  //右括号
            {
                //把'('之后的运算符全部从栈中弹出并压进队列
                while( '(' != operstack.top() )
                {
                    symbol += operstack.top();
                    exprdeq.push_back( symbol );
                    symbol.clear();
                    operstack.pop();
                }
                operstack.pop();  //弹出'('
            }
            else  //其他运算符
            {
                int oldprio, newprio = OperPriority( *s );
                if( newprio <= 0 )
                    return -1;
                oldprio = OperPriority( operstack.top() );
                if( newprio < oldprio )  //新的运算符优先级更高
                    operstack.push( *s );
                else
                {
                    symbol += operstack.top();
                    exprdeq.push_back( symbol );
                    symbol.clear();
                    operstack.top() = *s;
                }
            }
        }
    }

    //如果还有数字，那么还要把数字压进栈
    numlen = symbol.size();
    if( numlen > 0 )
    {
        exprdeq.push_back( symbol );
        symbol.clear();
        ++result;
    }

    //把剩余的运算符依次弹出栈并压进队列
    for( len = operstack.size(); len > 0; --len )
    {
        symbol += operstack.top();
        exprdeq.push_back( symbol );
        symbol.clear();
        operstack.pop();
    }

    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
                std::cout<<"\n<<< error: zero divisor!\n";
            break;
        case '%':
            result = (long)left % (long)right;
            break;
        case '^':
            result = pow( left, right );
            break;
        default:
            std::cout<<"\n<<< error: unknown operator "<<oper<<"!\n";
            break;
    }

    return result;
}

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

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

        input.clear();
        getline( std::cin, input );
        if( input.size() == 0 )
            return 0;

        for( i = 0; i < TRIM; ++i )
            input.erase( std::remove(input.begin(), input.end(), cleans[i]),
                         input.end() );

        numcount = transfer( input, exprdeq );

        if( numcount < 0 )
        {
            std::cout<<"<<< expression error!\n";
            continue;
        }

        //输出转换后的逆波兰表达式
        len = exprdeq.size();
        std::cout<<"<<< reverse Polish notation: ";
        for( i = 0; i < len; ++i )
            std::cout<<exprdeq[i]<<" ";
        std::cout<<std::endl;

        i = 0;
        while( !exprdeq.empty() )
        {
            if( exprdeq.front().size() == 1
                && !isdigit(exprdeq[0][0]) )  //运算符
            {
                if( i > numcount )
                {
                    val = calculate( valdeq[0], valdeq[1], exprdeq[0][0] );
                    valdeq.pop_front();
                    valdeq.pop_front();
                    valdeq.push_front( val );
                }
                else
                {
                    len = valdeq.size();
                    val = calculate( valdeq[len - 2], valdeq[len - 1],
                                     exprdeq[0][0] );
                    valdeq.pop_back();
                    valdeq.pop_back();
                    valdeq.push_back( val );
                    if( i == numcount )
                        ++i;
                }
            }
            else  //数字
            {
                val = atof( exprdeq.front().c_str() );
                valdeq.push_back( val );
                ++i;
            }
            exprdeq.pop_front();
        }

        std::cout<<"<<< "<<input<<" = "<<valdeq.front()<<std::endl;
        valdeq.clear();
    }

    return 0;
}