woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

使用c++的traits技术实现的任意类型元素的表达式求值

这里以整形和浮点型表达式为例。

#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;}};

//如果chdouble类型的合法前缀返回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;}};

//如果chdouble类型的合法前缀返回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;
    }
}

 

 

 

posted on 2008-11-08 22:51 肥仔 阅读(527) 评论(0)  编辑 收藏 引用 所属分类: C++ 模板


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理