posts - 16, comments - 0, trackbacks - 0, articles - 0

数据结构 四则运算

Posted on 2008-10-30 08:48 dengbo 阅读(457) 评论(0)  编辑 收藏 引用

#include 
"stdafx.h"
#include
"c1.h"
#include
"c3-1.h"
#include 
"bo3-1.h"
#include
<iostream>
#include
<stack>
#include
<vector>
#include
<string>

using namespace std;

/*******定义优先级**********/
/**
            +   -  *   /   (   ) (进栈符号)
(栈顶符号)
    
    +       >   >  <   <   <   >   

    -       >   >  <   <   <   >

    *       >   >  >   >   <   >

    /       >   >  >   >   <   >

    (       <   <  <   <   <   <

    )       >   >  >   >   >   >

**************************
*/

/*******  >  <  表示栈顶符号和要进栈符号的优先关系,
 如果 栈顶符号的优先级>要进栈符号的优先级,执行计算;
 如果 栈顶符号的优先级<要进栈符号的优先级,符号进栈**
*/


/*******返回栈顶符号是否优先与进栈符号*******/
char end[]="#";
bool is_prior_exe(char top, char in)
{
    
if(top == ')')
    
{
        
return true;
    }

    
if(top =='(')
        
return false;
    
if(top == '*' || top=='/')
    
{
        
if(in!='(')
            
return true;
        
else
        
{
            
return false;
        }

    }

    
if(top=='+' || top=='-')
    
{
        
ifin=='+' || in=='-' || in==')')
        
{
            
return true;
        }

        
if(in=='*' || in=='/' || in=='(')
        
{
            
return false;
        }

    }

}

bool In(char* c)
{
    
switch(c[0])
    
{
        
case'+':
        
case'-':
        
case'*':
        
case'/':
        
case'(':
        
case')':
        
case'#':return true;
        
default:return false;
    }

}

vector
<char *> get_word(string str)
{
    vector
<char *> word;
    
int i=0;
    
while(i<str.size())
    
{
        
if(str[i]=='('||str[i]==')'||str[i]=='*'||str[i]=='/'||str[i]=='+'||str[i]=='-')
        
{
            
char *temp = new char[2];
            temp[
0]=str[i];
            temp[
1]=='\0';
            word.push_back(temp);
        }

        
if((str[i]-'0'>=0 && str[i]-'0'<=9)||str[i]=='.')
        
{
            
static int j=-1;
            
static char *tmp;
            
if(j==-1)
            
{
                j
=i;
                tmp
=new char[15];

            }

            tmp[i
-j]=str[i];
            
if(i+1<str.size() && (str[i+1]-'0'<0 || str[i+1]-'0'>9)&&str[i+1]!='.')
            
{
                tmp[i
+1-j]='\0';
                word.push_back(tmp);
                j
=-1;
            }

            
else if(i+1==str.size())
            
{
                tmp[i
+1-j]='\0';
                word.push_back(tmp);
                j
=-1;
            }

        }

        i
++;
    }

    
    word.push_back(end);
    
return word;
}


double ConvertStrToDouble(char * exp)
{
    
//get integer 
    int num1=0;
    
while(*exp!='\0'&& *exp!='.')
    
{
        num1
=num1*10+ (*exp-'0');
        exp
++;
    }

    
if(*exp=='\0')
    
{
      
return  num1;
    }

    
//get decimal
    double num2=0;
    
while(*exp!='\0')
    
{
        
*exp++;
    }

    
*exp--;
    
while(*exp!='.')
    
{
        num2
=num2*0.1+(*exp-'0');
        
*exp--;
    }

    num2
=num2*0.1;
    
return num1+num2;
}




double Operate(double a,char theta, double b)
{
    
//int c;
    
//a=a-48;
    
//b=b-48;
    double c;
    
switch(theta)
    
{
    
case'+':c=a+b;
        
break;
    
case'-':c=a-b;
        
break;
    
case'*':c=a*b;
        
break;
    
case'/':c=a/b;
    }

    
return c;
        
}


char Precede(char t1, char t2)
{
    
char f;
    
switch(t2)
    
{
    
case'+':
    
case'-':if(t1=='(' || t1=='#')
                f
='<';
            
else
                f
='>';
        
break;
    
case'*':
    
case'/':if(t1=='*' || t1=='/' || t1==')')
                f
='>';
            
else
                f
='<';
        
break;
    
case'(':if(t1==')')
            
{
                printf(
"ERROR\n");
                exit(
0);
            }

            
else
                f
='<';
        
break;
    
case')':switch(t1)
            
{
                
case'(':f='=';
                    
break;
                
case '#':printf("ERROR2\n");
                    exit(
0);
                
default:f='>';
            }

            
break;
    
case'#':switch(t1)
            
{
                
case'#':f='=';
                    
break;
                
case'(':printf("ERROR3\n");
                    exit(
0);
                
default:f='>';

            }

    }

    
return f;
}


double EvaluateExpression(vector<char*> cpvec)
{

    stack
<char> OPTR;
    stack
<double>  OPND;
    
//SElemType a,b,c,x,theta;
    
//InitStack(&OPTR);
    
//Push(&OPTR,'#');
    double num_first,num_second;
    
char theta;
    OPTR.push (
'#');

    
//InitStack(&OPND);
    
//c=getchar();
    
//GetTop(OPTR,&x);
    char c_top = OPTR.top(); 
    
int i=0;
    
while(i<cpvec.size())
    
{
        
if(In(cpvec[i]))
        
{
            
char c_in = cpvec[i][0];
            
bool flg =false;
            
do
                

                    
switch(Precede(c_top,c_in))
                    
{
                        
case'<':OPTR.push(c_in) ;/*Stack top Prior lower Push Stack*/
                                c_top 
= OPTR.top();
                                flg
=false;
                                
break;
                        
case'=':OPTR.pop();/*off bracketd Pop Stack*/
                                
if(!(OPTR.empty()))
                                    c_top 
= OPTR.top();
                                flg
=false;
                                
break;
                        
case'>':theta=OPTR.top();
                            OPTR.pop(); 
/*Stack top Prior higher Pop Stack calculate*/
                            c_top
=OPTR.top();
                            num_first
=OPND.top();
                            OPND.pop(); 
                            num_second
=OPND.top();
                            OPND.pop();
                            OPND.push (Operate(num_second,theta,num_first));
                            flg
=true;
                            
break;
                    }

                }

            
while(flg);
        }

        
else if(cpvec[i][0>='0' && cpvec[i][0]<='9')/*c is number*/
        
{
            
double tmp = ConvertStrToDouble(cpvec[i]);
            OPND.push(tmp);            
        }

        
else /*c is illegal character*/ 
        
{
            printf(
"ERROR$\n");
            exit(
0);
        }

        
//GetTop(OPTR,&x);
        i++;
    }

    
    
return OPND.top();
}


int _tmain(int argc, _TCHAR* argv[])
{
    
//printf("Input a arithmetic expression use '#' to end");
    char ch;
    
while((ch=getchar())!=EOF)
    
{
        cout
<<"Input a arithmetic expression"<<endl;
        
string expstr;
        cin
>>expstr;
        vector
<char *>cpvec =get_word(expstr);
        cout
<<"result="<<EvaluateExpression(cpvec)<<endl;    
    }

    system(
"pause");
    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理