/**
*    This is a program for solve mathematical expression. Just like:
*            "1+4*3/2+22*(3+2*(3-4))"
*
*    To solve this problem, Let us see it by a view of priority. The rules as following:
*        1). the priority of plus sign is 1, and minus sign too.
*        2). the priority of product sign and sign of division is 2.
*        3). the priority of bracket is 3.
*
*    so, we can convert the expression above to:
*
*
*                                                                                 [1]
*                                                                                  .
*                                                                            -------------
*                                                                     [2]   .              .
*                                                           [1]        .    .              .
*                                                             .         .    .              .  
*                                                        --------------------------------
*                        [2]    [2]             [2]   .                                      .
*                [1]      .       .     [1]       .    .                                      .
*                 .        .       .      .         .    .                                      .
*           " 1  +  4  *  3  /  2  +  22  *    (  3  +  2  *   (  3  -  4   )   )  "
*
*    It is easy to know, we can‘t compute a sign in rising edge. And on the other way, we could dispose those brackets by a special way. that‘s means we could get a more

*    simple expression without bracket
*
*               [1]   [2]    [2]    [1]      [2]            [4]    [5]       [7]
*          " 1  +  4  *  3  /  2  +  22  *          3  +  2  *      3  -  4"
*
*    and then what we should to do is just as follow:
*
*        step 1: get a operator .
*        step 2: compare the priority with it‘s last one‘s.
*                    --   ‘>=‘ , compute it.
*                    --   ‘<‘ , return to the step above.
*
*    if arrvied the end , we will get a new expression. The priority of totally expression is increase by degree.
*
*                 [1]    [1]     [2]    [4]   [5]    [7]
*            " 1  +  6  +  22  *  3  +  2  *  3  - 4  "
*
*    In the last, what we need is compute all operator by inverted order.
*
*/

#include <iostream>#include <stdio.h>#include "../stack.h"#define NUMS_DEP	20#define SYMS_DEP	20/***    All input symbol must be one of the types. we will deal those symbol*    with a corresponding operation. Need to say, number is also belong to*    symbol.*/enum SYMBOL {        S_NUM,        S_PLUS,        S_SUB,        S_MUL,            //multiply        S_DIV,            //division        S_BRAL,        //left bracket        S_BRAR,        //right bracket        S_INVAID,        S_END,            // the end of expression        S_MAX,};/***    All symbols have a priority for operation.*/enum SYM_PRI {        PR_NUM = 0,        PR_INVALID = 0,        PR_PLUS = 1,        PR_SUB = 1,        PR_MUL = 2,        PR_DIV = 2,        PR_MAX,};/***    record information about symbol.  */struct OperatorS {        //what's type?        SYMBOL    sym;        //priority        int            prior;        //used to record the value of number.        int            val;};class Calculater {        public:                Calculater( );                ~Calculater( );                //initialize the environment                bool set( char *expr);                //solve                 bool work( void);                //show the result                void show( void);        private:                //deal with symbol                bool dwItem( OperatorS &item);                //get a symbol from the expression string                bool getItem( OperatorS &item);                //deal with bracket,                 bool adjustPri( OperatorS &item);                //modify the priority of a symbol                bool calcuPri( OperatorS &item);                //calculate the value of a symbol with its' corresponding values.                bool calcuSym( OperatorS &sym);                //convert a string to a interger                bool str2Inter( char *begin, int &val, int &len);                /*            * when deal with a symbol, we found it have a feature, first-in last-out.            * that is same as the feature of the stack.            */                //stack for save symbol                STACK<OperatorS>	sym_s;                //stack for save number                STACK<int>			num_s;                //mathematical expression                char *    expr;                //current position                int        cur_ind;                /*            * current priority. if encounter a bracket, this value will change for             * revise the priority of symbol after it.            */                int        cur_pri;                // the result will be restore in here.                int        sum;};Calculater::Calculater( ):num_s(NUMS_DEP),sym_s(SYMS_DEP){        this->expr = NULL;        this->cur_ind = 0;        this->cur_pri = 0;        this->sum = 0;}Calculater::~Calculater( ){}bool Calculater::set(char * expr){        this->expr = expr;        this->cur_ind = 0;        this->cur_pri = 0;        this->sum = 0;        return true;}/***	core function, work for solve the mathematical expression.*/bool Calculater::work( void){        OperatorS	item;/**    untill all of symbols be computed.*/        while( ('\0'!=this->expr[this->cur_ind])                        ||(this->num_s.getEleNum( )!=1) )        {                //get a symbol                        //Y: continue                        //N: remain the last symbol                if( !this->getItem( item) )                        return false;                //deal with symbol                this->dwItem( item);        }        this->num_s.pop( this->sum);        return true;}/***    get a item from the string, and build a symbol.*/bool Calculater::getItem( OperatorS & item){        char        firstc = this->expr[this->cur_ind];        this->cur_ind ++;        OperatorS    tmp;        switch( firstc)        {                case '+':                        tmp.sym = S_PLUS;                        tmp.prior = PR_PLUS;                        tmp.val = 0;                        break;                case '-':                        tmp.sym = S_SUB;                        tmp.prior = PR_SUB;			                        tmp.val = 0;                        break;                case '*':                        tmp.sym = S_MUL;                        tmp.prior = PR_MUL;                        tmp.val = 0;                        break;                case '/':                        tmp.sym = S_DIV;                        tmp.prior = PR_DIV;                        tmp.val = 0;                        break;                case '(':                        tmp.sym = S_BRAL;                        tmp.prior = PR_MAX;                        tmp.val = 0;                        break;                case ')':                        tmp.sym = S_BRAR;                        tmp.prior = PR_MAX;                        tmp.val = 0;                        break;                case '0'...'9':                {                        int    len = 0;                        tmp.sym = S_NUM;                        tmp.prior = PR_INVALID;                        this->str2Inter( this->expr + this->cur_ind - 1, tmp.val, len);                        this->cur_ind += len-1;                        break;                }                /*            *    when arrived the end, create a end sign.            */                case '\0':                {                        tmp.sym = S_END;                        tmp.prior = PR_INVALID;                        tmp.val = 0;                        break;                }                default :                        return false;                        break;        }        item = tmp;        return true;}/***    get a number from the string. if success, the value will*    be store in @val, and the length of reading will be store*    in @len.*/bool Calculater::str2Inter(char * begin,int & val,int & len){        int    tmp_val = 0;        int    tmp_len = 0;        while( (begin[tmp_len]>='0')                        &&(begin[tmp_len]<='9'))        {                tmp_val = tmp_val*10 + begin[tmp_len] - '0';                tmp_len++;        }        val = tmp_val ;        len = tmp_len ;        return true;}//deal with symbolbool Calculater::dwItem( OperatorS & item){        printf("sym: %x,	prior: %x,	val: %d\n", item.sym, item.prior, item.val);        switch( item.sym)        {                //case 1: symbol is a number.                        //push in @num_s.                case S_NUM :                        this->num_s.push( item.val);                        break;                //case 2: symbol is a operator.                case S_END:                case S_PLUS...S_DIV :                {                        //compute priority,  cur + = ()                        this->calcuPri( item);                        //compare with the last operator.                                    // <= , compute the last operator with the last two numbers.                                    //do the compare above untill the new operator greater than the last one.                                    // > , do nothing.                                    // * , push the new operator in @sym_s.                        //printf("sym: %x,	prior: %x,	val: %d\n", item.sym, item.prior, item.val);                        OperatorS    last;                        do{                                    if(!this->sym_s.pop( last))                                            break;    //there is no symbol                                     if( item.prior<=last.prior)                                    {                                            this->calcuSym( last);                                            continue;                                    }                                    this->sym_s.push( last);                            }                            while( item.prior <= last.prior);                            this->sym_s.push( item);                            break;                }                //deal with bracket                 case S_BRAL...S_BRAR:                {                        this->adjustPri( item);                        break;                }                default :                        return false;        }        return true;}bool Calculater::adjustPri(OperatorS & item){        switch( item.sym)        {                case S_BRAL:                        this->cur_pri += item.prior;                        break;                case S_BRAR:                        this->cur_pri -= item.prior;                        break;                default :                        return false;                        break;        }        return true;}/***    compute the priority of this symbol.*/bool Calculater::calcuPri( OperatorS & item){        switch( item.sym)        {                case S_END:                        break;                default :                        item.prior += this->cur_pri;                        break;        }	        return true;}bool Calculater::calcuSym(OperatorS & sym){        int    val1, val2, sum;        this->num_s.pop( val1);        this->num_s.pop( val2);        sum = 0;        switch( sym.sym)        {                case S_PLUS:                        sum = val2 + val1;                        break;                case S_SUB:                        sum = val2 - val1;                        break;                case S_MUL:                        sum = val2 * val1;                        break;                case S_DIV:                        sum = val2/val1;;                        break;                default :                        return false;                        break;        }        this->num_s.push( sum);        return true;}void Calculater::show(void){        printf(" %s = %d\n", this->expr, this->sum);}#define EXPR        "1+24*3/12-4*(5+6-7*2*(2+3*4))*22"int main(){        Calculater	    cal;        cal.set( EXPR);        cal.work( );        cal.show( );        return 0;}