posts - 176, comments - 60, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
这里以整形和浮点型表达式为例。

#include <iostream>
#include 
<string>
#include 
<cmath>
#include 
<sstream>
#include 
<stack>
#include 
<queue>
using namespace std;

template 
<typename T>struct Type{static bool isPrefix(char ch){return 0;}};

//如果ch是double类型的合法前缀返回true,否则返回false
template <> struct Type<double>{
    
static bool isPrefix(char ch){
        
return ch=='.' || isdigit(ch);
    }
};

template 
<> struct Type<int>{
    
static bool isPrefix(char ch){
        
return isdigit(ch);
    }
};

template 
<class T>
class Expression{
    
string instr;
    queue
<T> Q;
public:
    
//用字符串str初始化表达式
    Expression(string str){instr=str;}

    
//返回表达式的值
    T value(){return eval(postfix(instr));}

    
static int prcd(char c1,char c2)
    {
//当c1的运算先于c2时返回真,否则返回假
        if(c1=='^' &&c2=='^')return 0;
        
if(c1=='(')return 0;
        
if(c2==')')return 1;
        
if(c2=='(')return 0;
        
static char *str[]={"+-","*/","^",NULL};
        
int i1=0,i2=0;
        
for(int i=0;str[i];i++){
            
for(int j=0;str[i][j];j++){
                
if(str[i][j]==c1)i1=i;
                
if(str[i][j]==c2)i2=i;
            }
        }
        
return (i1>=i2);
    }

    
string postfix(string instr)
    {
//返回中缀表达式instr的后缀表达式,其中的操作数用o代替,并存入队列Q 
        istringstream iss(instr);//输入流
        ostringstream oss;
        stack
<char> S;
        
for (char ch;iss>>ch;){
            
if(Type<T>::isPrefix(ch)){
                iss.unget();
                T s;
                iss
>>s;
                oss
<<'o';
                Q.push(s);
            }
            
else {
                
while(!S.empty() && prcd(S.top(),ch)){
                    oss
<<S.top();S.pop();
                }
                
if(ch!=')') S.push(ch);
                
else S.pop();
            }
        }
        
while(!S.empty()){
            oss
<<S.top();S.pop();
        }
        
return oss.str();
    }

    
static T oper(char symb,T& ta,const T& tb)
    {
        
switch(symb){
        
case '+':return ta+=tb;
        
case '-':return ta-=tb;
        
case '*':return ta*=tb;
        
case '/':return ta/=tb;
        
case '^':return ta=(T)pow(ta,(double)tb);
        
default:
            cerr
<<"未定义的运算符:"<<symb<<endl;exit(1);
        }
    }

    T eval(
string poststr)
    {
//返回后缀表达式poststr的值
        istringstream iss(poststr);//输入流
        stack<T> S;
        
for (char ch;iss>>ch;){
            
if(ch=='o'){
                T v
=Q.front();Q.pop();
                S.push(v);
            }
            
else{
                T tb
=S.top();S.pop();
                oper(ch,S.top(),tb);
            }
        }
        T t
=S.top();S.pop();
        
return t;
    }
};

int main()
{
    
string line;
    
while(getline(cin, line)){
        Expression
<double> e(line);
        cout
<< e.value() <<endl;
        Expression
<int> e2(line);
        cout
<< e2.value() <<endl;
    }
}

不止如此,它还可以实现自定义类型的表达式的求值,下面是一个对自定义集合类型的交、并、补运算进行求值。
问题的描述见(http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=958 title:friends)

#include <iostream>
#include 
<algorithm>
#include 
<vector>
#include 
<string>
#include 
<cmath>
#include 
<sstream>
#include 
<cstdlib>
#include 
<stack>
#include 
<queue>
using namespace std;

struct Set{
    unsigned 
int date;
    Set(){}
    Set(
const Set& b){date=b.date;}

    Set
& operator += (const Set& b){
        date
|=(b.date);
        
return *this;
    }

    Set
& operator *= (const Set& b){
        date
&=(b.date);
        
return *this;
    }

    Set
& operator -= (const Set& b){
        date
&=(~b.date);
        
return *this;
    }

    Set 
operator - (){
        date
=~date;
        date
&=((1<<26)-1);
        
return *this;
    }
    friend istringstream
& operator >> (istringstream& ss,Set& obj);
    friend ostream
& operator << (ostream& os,const Set& obj);
};

template 
<typename T>struct Type{static bool isPrefix(char ch){return 0;}};

//如果ch是double类型的合法前缀返回true,否则返回false
template <> struct Type<Set>{
    
static bool isPrefix(char ch){
        
return ch=='{';
    }
};

istringstream
& operator >> (istringstream& ss,Set& obj){
    obj.date
=0;
    
char ch;
    ss
>>ch;//去掉{
    while(ss>>ch,ch!='}'){
        obj.date
|= (1<<(ch-'A'));
    }
    
return ss;
}

ostream
& operator << (ostream& os,const Set& obj){
    os
<<'{';
    
for(int i=0;i<26;i++){
        
if(obj.date&(1<<i)){
            os
<<(char)('A'+i);
        }
    }
    os
<<'}';
    
return os;
}

template 
<class T>
class Expression{
    
string instr;
    queue
<T> Q;
public:
    
//用字符串str初始化表达式
    Expression(string str){instr=str;}

    
//返回表达式的值
    T value(){return eval(postfix(instr));}

    
static int prcd(char c1,char c2)
    {
//当c1的运算先于c2时返回真,否则返回假
        if(c1=='^' &&c2=='^')return 0;
        
if(c1=='(')return 0;
        
if(c2==')')return 1;
        
if(c2=='(')return 0;
        
static char *str[]={"+-","*/","^",NULL};
        
int i1=0,i2=0;
        
for(int i=0;str[i];i++){
            
for(int j=0;str[i][j];j++){
                
if(str[i][j]==c1)i1=i;
                
if(str[i][j]==c2)i2=i;
            }
        }
        
return (i1>=i2);
    }

    
string postfix(string instr)
    {
//返回中缀表达式instr的后缀表达式,其中的操作数用o代替,并存入队列Q 
        istringstream iss(instr);//输入流
        ostringstream oss;
        stack
<char> S;
        
for (char ch;iss>>ch;){
            
if(Type<T>::isPrefix(ch)){
                iss.unget();
                T s;
                iss
>>s;
                oss
<<'o';
                Q.push(s);
            }
            
else {
                
while(!S.empty() && prcd(S.top(),ch)){
                    oss
<<S.top();S.pop();
                }
                
if(ch!=')') S.push(ch);
                
else S.pop();
            }
        }
        
while(!S.empty()){
            oss
<<S.top();S.pop();
        }
        
return oss.str();
    }

    
static T oper(char symb,T& ta,const T& tb)
    {
        
switch(symb){
        
case '+':return ta+=tb;
        
case '-':return ta-=tb;
        
case '*':return ta*=tb;
        
//case '/':return ta/=tb;
        
//case '^':return ta=(T)pow(ta,(double)tb);
        default:
            cerr
<<"未定义的运算符:"<<symb<<endl;exit(1);
        }
    }

    T eval(
string poststr)
    {
//返回后缀表达式poststr的值
        istringstream iss(poststr);//输入流
        stack<T> S;
        
for (char ch;iss>>ch;){
            
if(ch=='o'){
                T v
=Q.front();Q.pop();
                S.push(v);
            }
            
else{
                T tb
=S.top();S.pop();
                oper(ch,S.top(),tb);
            }
        }
        T t
=S.top();S.pop();
        
return t;
    }
};


int main()
{
    
string line;
    
while(getline(cin, line)){
        Expression
<Set> e(line);
        cout
<< e.value() <<endl;
    }
}

只有注册用户登录后才能发表评论。