在1 2 3 4 5 6 7 8 9九个数字中插入“+”或“-”符号使得结果为100，编程实现所有的组合。
注：数字的顺序不能改变。
如： 123 - 45 - 67 + 89 = 100
      12 - 3 -4 + 5 - 6 + 7 + 89 = 100

原帖索引：http://topic.csdn.net/u/20080504/15/57909a01-1989-43d2-bff0-d104e34e5a97.html

当时飞雪同学很快给出代码，令我钦佩不已。当即请教飞雪的代码，然而他提到“语法分析”时，我却大惑不解。。。
#include <iostream>   
using namespace std;   
class CAL   
{   
    enum{NUMBER, OPERATOR, END, UNKNOWN};   
    class Token   
    {   
    public:   
        int    value;   
        int    type;   
    };   
    const char*    buff;   
    int        curr;   
    Token    tk;   
public:   
  
    int        Evalue(const char* exp)   
    {   
        int value = 0;   
        int    sign = 1;   
        buff = exp;   
        curr = 0;   
        do{   
            MoveToNextToken();   
            switch (tk.type)   
            {   
            case    NUMBER: value += sign * tk.value;break;   
            case    OPERATOR: sign = tk.value == '+' ? 1 : -1;   
            }   
        }while (tk.type==NUMBER||tk.type==OPERATOR);   
        return value;   
    }   
    void    MoveToNextToken()   
    {   
        static char temp[256];   
        tk.type = UNKNOWN, tk.value = 0;   
  
        if (!buff[curr])    
        {   
            tk.type = END;   
            return;   
        }   
        if (buff[curr]>='0'&&buff[curr]<='9')   
        {   
            int value = 0;   
            while (buff[curr]&&buff[curr]>='0'&&buff[curr]<='9')   
                value = value * 10 + buff[curr++] - '0';   
            tk.value = value;   
            tk.type = NUMBER;   
            return;   
        }   
        switch (buff[curr++])   
        {   
        case '+':   
            tk.type = OPERATOR, tk.value = '+';return;   
        case '-':   
            tk.type = OPERATOR, tk.value = '-';return;   
        }   
           
        tk.type = UNKNOWN;   
        return;   
    }   
};   
void    DelSpace(char* str)   
{   
    char* curr = str;   
    while (*curr=*str++)   
        if (*curr!=' ') curr++;   
}   
void    GetExpression(int a[], int n)   
{   
    static char token[] = {'+','-',' '};   
    static char buff[256];   
    static CAL    cal;   
       
    sprintf(buff, "1%c2%c3%c4%c5%c6%c7%c8%c9",   
        token[a[0]], token[a[1]], token[a[2]], token[a[3]],   
        token[a[4]], token[a[5]],token[a[6]], token[a[7]]);   
    DelSpace(buff);   
    //    cout << buff << endl;   
    int    result = cal.Evalue(buff);   
    if (result == 100)   
        cout << buff << '=' << result << endl;   
}   
void    DoEnum(int n, int curr, int to[])   
{   
    if (curr == n)   
    {   
        GetExpression(to, n);   
    }   
    else  
    {   
        for (int i = 0; i < 3; ++i)   
        {   
            to[curr] = i;   
            DoEnum(n, curr+1, to);   
        }   
    }   
}   
int main()   
{   
    int to[8];   
    DoEnum(8, 0, to);   
    return 0;   
}  

时至2008年底偶们终于开了编译原理这门课，在此期间如饥似渴的汲取着编译原理的知识。反过来重新看待这个帖子，发现飞雪的代码写的真好，真是把编译原理学活了，，，然而书到此处，总感觉代码的局限性不是很爽，就是只填了加减，那么要是填入 “+”“-”“*”“、”“（”“）”时呢

 

首先，我们来考虑表达式的计算，虽然飞雪的代码只能处理加减（也许在他的cal.h��:u �on�c�P0的就是语义分析，然而语义分析我们一般使用语法制导翻译，也就是说这里语法分析仍然是重点

语法分析一般是两种，自上而下分析法和自下而上分析法。自上而下分析法一般有递归下降和预测分析表两种方法，预测分析表法应该是比较常用的，因为可以自动生成，然而递归下降法有其一个有点就是，代码比较容易理解，这里我就给出了一个递归下降的代码。。

递归下降的：这是我们的上机练习题

// CC1.cpp : 定义控制台应用程序的入口点。   
#include "stdafx.h"   
#include<cstdlib>   
#include<iostream>   
using namespace std;   
char prog[80]="5-2*(3-7)*10#";   
int i=0,kk=0;//语法分析使用   
int synv[50]={0};//词法语法共用   
char chsyn[50][20];//词法语法共用   
struct Quad   
{   
    char op[8];   
    char ag1[8];   
    char ag2[8];   
    char result[8];   
%�:u �on�c�PB='9'&&ch>='0'))   
            {   
                sum=sum*10+ch-'0';   
                ch=prog[p++];   
            }   
            syn=11;   
            --p;   
        }   
    else  
        {   
        switch(ch)   
            {   
        case'<':m=0;   
                token[m++]=ch;   
                ch=prog[p++];   
                if(ch=='>')   
                {   
                    syn=21;   
                    token[m]=ch;   
                }   
                else if(ch=='=')   
                {   
                    syn=22;   
                    token[m]=ch;   
                }   
                if(ch=='>')   
                {   
                    syn=21;   
                    --p;   
                }   
                break;   
        case'>':m=0;   
                token[m++]=ch;   
                ch=prog[++p];   
                if(ch=='=')   
                {   
                    syn=24;   
                    token[m]=ch;   
                }   
                else  
                {   
                    syn=23;   
                    --p;   
                }   
                break;   
        case':':m=0;   
                token[m++]=ch;   
                ch=prog[p++];   
                if(ch=='=')   
                {   
                    syn=18;   
                    token[m]=ch;   
                }   
                else  
                {   
                    syn=17;   
                    --p;   
                }   
                break;   
        case'+': syn=13;   
                token[0]=ch;   
                 break;   
        case'-': syn=14;   
                token[0]=ch;   
                 break;   
        case'*': syn=15;   
                token[0]=ch;   
                 break;   
        case'/': syn=16;   
                token[0]=ch;   
                 break;   
        case';': syn=26;   
                token[0]=ch;   
                 break;   
        case'(': syn=27;   
                token[0]=ch;   
                 break;   
        case')': syn=28;   
                token[0]=ch;   
                 break;   
        case'#': syn=0;   
                token[0]=ch;   
                 break;   
        default:syn=-1;   
            }   
        }   
    switch(syn)   
            {   
            case 11:   
                printf("(%d,%d)\n",syn,sum);   
                strcpy(chsyn[++cnumber],itoa(sum,localch,10));   
                break;//输出（数的二元组）；   
            case -1:printf("error\n");   
                break;   
            default:printf("(%d,%s)\n",syn,token);   
                strcpy(chsyn[++cnumber],token);   
                break;//输出（关键字begin的二元组）；break;   
            }   
  } while(syn!=0);   
  printf("\n");   
}   
int expression()   
{   
  
    int _add_result=0;   
    int _add_first_place=term();   
    while(synv[i]==13||synv[i]==14)   
    {   
        char _add_ch=chsyn[i][0];   
        ++i;   
        int _add_second_place=term();   
        _add_result=call_cal(_add_ch,_add_first_place,_add_second_place);   
        add_emit(_add_ch,_add_first_place,_add_second_place,_add_result);   
        _add_first_place=_add_result;   
    }   
    return _add_first_place;   
}   
int term()   
{      
    int add_first_place=factor();   
    int add_result=0;   
    while(synv[i]==15||synv[i]==16)   
    {   
        char add_ch=chsyn[i][0];   
        ++i;   
        int add_second_place=factor();   
        add_result=call_cal(add_ch,add_first_place,add_second_place);   
        add_emit(add_ch,add_first_place,add_second_place,add_result);   
        add_first_place=add_result;   
    }   
    return add_first_place;   
}   
  
int factor()   
{   
    int add_num=0;   
    if(synv[i]==10)   
    {   
      ++i;   
    }   
    else if(synv[i]==11)   
    {   
         add_num=atoi(chsyn[i]);   
          ++i;   
    }   
    else if(synv[i]==27)//'('   
    {   
        ++i;   
         add_num=expression();   
        if(synv[i]==28)//')'   
            ++i;   
        else  
        {   
            printf(") error\n");   
            kk=1;   
        }   
    }   
    else  
    {   
        printf("factor synax error\n");   
        kk=1;   
    }   
    return add_num;   
}  

自下而上分析法一般有算符优先分析法和LR分析法（LR里面又包括很多）。算符优先分析法有一个局限性就是它只能处理算符优先文法，这里我给出一个算符优先的代码，说是算符优先，其实就是逆波兰式，因为我在写代码的过程中发现它们本质上是一样的,这是当时的感想，现在贴出来
所谓的逆波兰式是根据算符优先文法的分析而来的。。   
  
算符优先算法是比较所有终结符的的优先级，而逆波兰式构造时只是   
将数字特殊化处理，比较算符的优先级。。   
  
所以说算符优先文法和逆波兰式的区别也就是逆波兰式只是算符优先文法的一种   
特殊情况罢了。  

 LR文法是应用非常广的一种文法，一般都是自动生成的（需要构造表，分析法也是固定的）。。我下载了一个Parser Generator2，然后准备将生成的代码该一下，以其能够从一个string接受参数，然而可能是我的编译器的原因，生成的代码一直无法通过编译，也就无果而终了。。

这个是逆波兰式的;

#include "stdafx.h"   
#include<iostream>   
#include <stack>   
#include <queue>   
#include <string>   
using namespace std;   
enum{NUMBER, OPERATOR, END, UNKNOWN};   
class Token   
{   
public:   
 int value;   
 char opeor;   
 int type;   
 Token(int _value=0,int _opeor='#',int _type=UNKNOWN)   
  :value(_value),opeor(_opeor),type(_type){}   
};   
Token t[20];   
int por(char ch)   
{   
 switch(ch)   
 {   
 case '(':   
 case '#': return 0;   
 case '+':   
 case '-': return 1;   
 case '*':   
 case '/': return 2;   
 default:return -1;   
 }   
}   
  
  
void Ctpostexp(string str,queue<Token>& q)   
{   
  stack<char> s_ch;   
  s_ch.push('#');   
 int i=0,index_t=0,sum=0;   
 char ch=str[i];   
while(i<str.size())   
 {   
  sum=0;   
  ch=str[i];   
  if((ch<='9'&&ch>='0'))   
  {   
   while((ch<='9'&&ch>='0'))   
   {   
    sum=sum*10+ch-'0';   
    ch=str[++i];   
   }   
   t[index_t].type=NUMBER;   
   t[index_t].value=sum;   
   q.push(t[index_t]);   
   ++index_t;   
  }   
  else  
  {   
   if(por(str[i])>por(s_ch.top()))   
   {   
    s_ch.push(str[i]);   
   }   
   else if(str[i]=='(')   
   {   
    s_ch.push(str[i]);   
   }   
   else if(str[i]==')')   
   {   
    while(s_ch.top()!='(')   
    {   
    t[index_t].type=OPERATOR;   
    t[index_t].opeor=s_ch.top();   
    q.push(t[index_t]);   
    s_ch.pop();   
    }   
    s_ch.pop();   
   }   
   else if(str[i]=='#')   
   {   
    while(s_ch.top()!='#')   
    {   
    t[index_t].type=OPERATOR;   
    t[index_t].opeor=s_ch.top();   
    q.push(t[index_t]);   
    s_ch.pop();   
    }   
    s_ch.pop();   
   }   
   else if(por(str[i])<=por(s_ch.top()))   
   {   
    t[index_t].type=OPERATOR;   
    t[index_t].opeor=s_ch.top();   
    q.push(t[index_t]);   
    s_ch.pop();   
    s_ch.push(str[i]);   
   }   
   ++i;   
   ++index_t;   
  }   
     
 }   
}   
int Calpostexp(queue<Token>& q)   
{   
 stack<int> s_int;   
 while(!q.empty())   
 {   
  int a=0,b=0;   
  if(q.front().type==NUMBER)   
  {   
   s_int.push(q.front().value);   
   q.pop();   
  }   
  else if(q.front().type==OPERATOR)   
  {   
   char ch_op=q.front().opeor;   
   switch(ch_op)   
   {   
   case '+':    
     a=s_int.top();   
     s_int.pop();   
     b=s_int.top();   
     s_int.pop();   
     s_int.push(b+a);   
     break;   
   case '-':    
     a=s_int.top();   
     s_int.pop();   
     b=s_int.top();   
     s_int.pop();   
     s_int.push(b-a);   
     break;   
   case '*':    
     a=s_int.top();   
     s_int.pop();   
     b=s_int.top();   
     s_int.pop();   
     s_int.push(b*a);   
     break;   
   case '/':    
     a=s_int.top();   
     s_int.pop();   
     b=s_int.top();   
     s_int.pop();   
     s_int.push(b/a);   
     break;   
   default:break;   
       
   }   
   q.pop();   
  }   
  else    
  {   
   cout<<"error";break;   
  };   
 }   
 int num=s_int.top();   
 return num;   
}   
int _tmain(int argc, _TCHAR* argv[])   
{   
  
 queue<Token>q;   
 string str("2*3+5#");   
 Ctpostexp(str,q);   
 /int result = Calpostexp(q);   
 cout<<result<<endl;   
 return 0;   
}