這里以整形和浮點型表達式為例。
#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;
}
}