【编译原理】逆波兰式的产生及计算：C/C++实现-阿里云开发者社区

1. 编译原理之逆波兰式的产生及计算概念

1.1 编译原理

编译原理是计算机科学领域的一个重要分支，它研究如何将高级编程语言的源代码转化成计算机能够执行的机器代码或中间代码的过程。编译原理涵盖了编译器的设计和实现，其中编译器是一种将源代码翻译成目标代码的软件工具。编译器的主要任务包括语法分析、词法分析、语义分析、优化和代码生成等环节。

1.2 逆波兰式的产生及计算

逆波兰式（Reverse Polish Notation，RPN），也称为后缀表达式，是一种用于表示数学表达式的形式，其特点是操作符位于与之相关的操作数之后。相比传统的中缀表达式，逆波兰式更容易被计算机程序理解和处理。

🔥资源获取：关注文末公众号回复逆波兰式的产生及计算源码

🔥相关博文：编译原理之LR(1)分析法：C/C++实现（附源码+详解！）

2. 逆波兰式的产生及计算

2.1 实验目的

（1）使用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式；

（2）计算用逆波兰式来表示的算术表达式的值。

2.2 实验要求

如输入

21+（（42-2）*15+6 ）-18#

则输出为：

原来表达式： 21+（（42-2）*15+6  ）- 18#
         后缀表达式：21&42&2&-15&*6&++18&-
         计算结果：609

2.2.1 算法流程图

2.2.2 参考程序代码

参考代码（不完整）：

逆波兰式生成：
while(ch!='#')
      {switch(ch)
    { case '(':top++;stack[top]=ch; break;
      case ')':while(stack[top]!='('){ ex[t]=stack[top];top--;t++;}
         top--;
         break;
      case '+':
      case '-':
        while(top!=0&&stack[top]!='(')
          { ex[t]=stack[top];top--;t++;}
      top++;stack[top]=ch;break;
      case '*':
      case '/':
        while(stack[top]=='*'||stack[top]=='/')
          { ex[t]=stack[top];top--;t++;}
      top++;stack[top]=ch;break;
      case ' ':break;
      default:
        while(ch>='0'&&ch<='9'){ex[t]=ch;t++;ch=str[i];i++;}
        i--;
        ex[t]='&';t++;
    }
   ch=str[i];i++;
   }
   while(top!=0)
     if(stack[top]!='(')
         { ex[t]=stack[top];t++;top--;}   else {printf("error");top--; exit(0); }
计算逆波兰式：
  while(ch!='#')
   { switch(ch)
  {  case '+':  stack[top-1]=stack[top-1]+stack[top];top--;break;
     case '-':  stack[top-1]=stack[top-1]-stack[top];top--;break;
     case '*':  stack[top-1]=stack[top-1]*stack[top];top--;break;
     case '/':
          if(stack[top]!=0)
      stack[top-1]=stack[top-1]/stack[top];
          else
      {
        printf("\n\tchu0error!\n");
        exit(0);
      }
          top--;break;
     default:
          d=0;
          while(ch>='0'&&ch<='9')
           { d=10*d+ch-'0';
       ch=ex[t];t++;
           }
          top++;
                stack[top]=d;
  }

2.3 实验内容

2.3.1 实验解决代码

根据参考代码修改如下：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
const char* yunsf[6] = {"+","-","*","/","^","%"};
struct Expression{  //表达式结构体
  char expre[6];
  int length;
  int logo; //0表示整数，1表示浮点数，2表示字符 
};
struct Polish{
  int int_num;
  float float_num;
  char calcu[4];
  int calcu_length;
  int logo; //0表示整数，1表示浮点数，2表示字符 
};
char user_string [20]; //存储用户输入的中缀表达式
Polish struct_hou[20]; //存储逆波兰表达式
Expression lexical_expre[20]; //存储词法分析之后的结果
char omega_stack[20]; //分析栈
int omega_pointer; //分析栈的指针
int zhong_leng; //中缀表达式的长度 
int length_lexical; //经词法分析之后的数组的长度 
int hou_leng; //逆波兰表达式的长度 
int float_flag = 0; //0表示没有输入小数，1表示输入小数 
struct Polish result; //最终计算结果
bool input_string();
void translate();
void calculate();
void init();
void lexical_analysis();
int digitProcess(char buffer,int pointer);
int calcuProcess(char buffer,int pointer);
bool isDigit(char buffer);
bool isCalcu(char buffer);
void translate();
int string_to_int(char *str,int length);
float string_to_float(char *str,int length);
int main(){
  bool input_correctly = false;
  while(!input_correctly){
    input_correctly = input_string();
  }
  init();
  lexical_analysis();
  translate();
  printf("后缀表达式：");
  for(int i = 0; i<hou_leng;i++){
    if(struct_hou[i].logo==0 && struct_hou[i].int_num<0){
      printf("%d - ",struct_hou[i].int_num*(-1));
    }
    else if(struct_hou[i].logo==0){
      printf("%d ",struct_hou[i].int_num);
    }
    else if(struct_hou[i].logo==1){
      printf("%.2f ",struct_hou[i].float_num);
    }
    else{
      printf("%s ",struct_hou[i].calcu);
    }
  }
  printf("\n");
  calculate();
  if(float_flag){
    printf("计算结果：%.2f\n",result.float_num);
  }
  else{
    printf("计算结果：%d\n",result.int_num);
  }
}
void translate(){ //将中缀表达式转换为后缀 
  int struct_point = 0;
  while(struct_point<length_lexical){ //当词法分析结果栈还有内容时
    struct Expression expre_trans = lexical_expre[struct_point];
    //omega_stack栈中只存储运算符
    if(strcmp(expre_trans.expre,"(")==0){
      //如果是左括号，直接入栈
      omega_stack[++omega_pointer] = '(';
    }
    else if(strcmp(expre_trans.expre,")")==0){
      //如果是右括号，则一直出栈，直到栈顶是左括号
      while(omega_stack[omega_pointer]!='('){
        struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
        hou_leng++;
        omega_pointer--;
      }
      omega_pointer--;
    }
    else if(strcmp(expre_trans.expre,"^")==0){
      omega_stack[++omega_pointer] = expre_trans.expre[0]; //如果是乘除取余符号，则expre_trans中的字符长度为1 
    }
    else if(strcmp(expre_trans.expre,"*")==0 || strcmp(expre_trans.expre,"/")==0||strcmp(expre_trans.expre,"%")==0){
      //如果是乘除符号和取余符号 
      //则把全部*/%符号都出栈（相当于：在左边的*/号的优先级比后面的*/的优先级高） 
      while(omega_stack[omega_pointer]=='*'||omega_stack[omega_pointer]=='/'||omega_stack[omega_pointer]=='%'||omega_stack[omega_pointer]=='^'){
        struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
        hou_leng++;
        omega_pointer--;
      }
      //将刚才的*/%号入栈
      omega_stack[++omega_pointer] = expre_trans.expre[0]; //进栈 
    }
    else if(strcmp(expre_trans.expre,"+")==0 || strcmp(expre_trans.expre,"-")==0){
      //如果是加减符号
      if(struct_point==0||(strcmp(lexical_expre[struct_point-1].expre,"(")==0)){
        //如果正负号在第一位，则说明是单目运算符 
        //如果加减符号的前一个符号为(，则说明是单目运算符。
        if(lexical_expre[struct_point+1].logo==0){ //如果下一个是整数 
          //如果是整数
          struct_hou[hou_leng].int_num =0-string_to_int(lexical_expre[struct_point+1].expre,lexical_expre[struct_point+1].length);
          struct_hou[hou_leng].logo = 0;
          hou_leng++;
        }
        else if(lexical_expre[struct_point+1].logo==1){ //如果下一个是浮点数 
          //如果是浮点数
          struct_hou[hou_leng].float_num =0-string_to_float(lexical_expre[struct_point+1].expre,lexical_expre[struct_point+1].length);
          struct_hou[hou_leng].logo = 1;
          hou_leng++;
        }
        else{
          printf("格式输入错误！\n");
          exit(0);
        }
        struct_point++;
      }
      else{
        //由于该+-号的优先级最低，只比(高，因此使所有栈中的字符都出栈，直至符号为(
        while(omega_pointer!=-1&&omega_stack[omega_pointer]!='('){
          struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
          hou_leng++;
          omega_pointer--;
        }
        //将新的加减符号入栈
        omega_stack[++omega_pointer] = expre_trans.expre[0]; //如果是加减符号，则expre_trans中的字符长度为1
      }
    }
    else{//非运算符 
      //说明是数字
      if(expre_trans.logo==0){
        //如果是整数
        struct_hou[hou_leng].int_num = string_to_int(expre_trans.expre,expre_trans.length);
        struct_hou[hou_leng].logo = 0;
        hou_leng++;
      }
      else{
        //如果是浮点数
        struct_hou[hou_leng].float_num = string_to_float(expre_trans.expre,expre_trans.length);
        struct_hou[hou_leng].logo = 1;
        hou_leng++;
      }
    }
    struct_point++;
  }
  while(omega_pointer!=-1){
    //当表达式扫描完毕后， 假如omage分析栈还存在元素，就依次全部加入到Polish栈中。 
    if(omega_stack[omega_pointer]!='('){
      struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
      hou_leng++;
    }
    else{
      printf("输入的表达式错误！\n");
      exit(0);
    }
    omega_pointer--;
  }
}
void calculate(){ //计算后缀表达式 
  int struct_point = 0;
  while(struct_point<hou_leng){ //当逆波兰结果数组中还有内容时 
    struct Polish polish = struct_hou[struct_point];
    if (strcmp(polish.calcu,"+")==0){
      //如果是加号
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num+struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      //如果有一方是浮点数
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-1].float_num+temp;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = temp + struct_hou[struct_point-2].float_num;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num+struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"-")==0){
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num-struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = temp-struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num-temp;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num-struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"*")==0){
//      printf("进入乘号页面！\n");
      //如果是乘号 
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num*struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-1].float_num*temp;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = temp*struct_hou[struct_point-2].float_num;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num*struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
      else if (strcmp(polish.calcu,"^")==0){ 
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = pow(struct_hou[struct_point-2].float_num,struct_hou[struct_point-1].float_num);
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = pow(struct_hou[struct_point-1].float_num,temp);
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = pow(temp,struct_hou[struct_point-2].float_num);
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = pow(struct_hou[struct_point-2].int_num,struct_hou[struct_point-1].int_num);
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"/")==0){
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num/struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num =temp/struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num/temp;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num/struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"%")==0){
      if(struct_hou[struct_point-1].logo==1||struct_hou[struct_point-2].logo==1){
        printf("浮点数不可以进行取整运算！\n");
        exit(0);
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num % struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    if(polish.logo==2){
      for(int i = struct_point-2;  i<hou_leng-2; i++){
        struct_hou[i] = struct_hou[i+2];
      }
      struct_point = struct_point-2;
      hou_leng = hou_leng-2;
    }
    struct_point++;
  }
  result.float_num = struct_hou[0].float_num;
  result.int_num = struct_hou[0].int_num;
}
void lexical_analysis(){
  //对用户输入的串进行词法分析
  int pointer = 0;  //暂时的、只用于词法分析的指针 
    while (pointer<zhong_leng){ //当还有剩下的字符时
      char cbuffer = user_string[pointer];
        if(cbuffer==' '||cbuffer=='\n'||cbuffer=='  '){
      /*掠过空格和回车符*/
    } 
      else if(cbuffer=='('||cbuffer==')'){ //括号单独拿出来处理 
        lexical_expre[length_lexical].expre[lexical_expre[length_lexical].length++]=cbuffer;
      length_lexical++;
      pointer++;
    }
      else if(isDigit(cbuffer)){ //处理常数 
          pointer = digitProcess(cbuffer,pointer);
      }
    else if(isCalcu(cbuffer)){ //处理算术运算符 
        pointer = calcuProcess(cbuffer,pointer);
    }
    else{
      printf("输入了不正确的字符！\n");
      exit(0);
    }
    }
  return ;
}
int digitProcess(char buffer,int pointer){
  //处理数字
  int flag = 0;//0表示没有小数点，1表示有小数点 
  while (isDigit(buffer)||buffer=='.'){
    if(buffer=='.'){
      flag=1;
    }
    lexical_expre[length_lexical].expre[lexical_expre[length_lexical].length++] = buffer;
      buffer = user_string[++pointer];
  }
  if(flag){
    //如果有小数点
    lexical_expre[length_lexical].logo = 1;  //将类型置为浮点数 
    float_flag = 1; //说明有小数，要按照浮点数的运算规则进行计算 
  }
  else{
    lexical_expre[length_lexical].logo = 0; //将类型置为整形 
  }
  length_lexical++;
  return pointer;
}
int string_to_int(char *str,int length){
  int result = 0;
  for(int i = 0; i<length; i++){
    result = result*10+(int)(str[i]-'0');
  }
  return result;
}
float string_to_float(char *str,int length){
  int result_int = 0;
  float result_float = 0;
  int i=0;
  for(i; i<length; i++){
    if(str[i]=='.'){
      break;
    }
    result_int = result_int*10+(int)(str[i]-'0');
  }
  float decimal = 0.1; 
  for(i=i+1; i<length; i++){
    float temp = (int)(str[i]-'0');
    result_float = result_float+temp*decimal;
    decimal*=0.1;
  }
  float temp_int = result_int;
  return temp_int+result_float;
}
int calcuProcess(char buffer,int pointer){
  while ((isCalcu(buffer))){
    lexical_expre[length_lexical].expre[lexical_expre[length_lexical].length++]=buffer;
      buffer=user_string[++pointer];
  }
  //检查该操作符是否在预设的符号之中
  int flag = 0; //0表示不在，1表示在 
  for (int i = 0;i<6;i++){
    if(strcmp(lexical_expre[length_lexical].expre,yunsf[i])==0){
      flag = 1;
    }
  }
  if(!flag){
    printf(" %s 输入错误！\n",lexical_expre[length_lexical].expre);
    exit(0);
  }
  length_lexical++;
  return pointer;
}
void init(){
  //进行一些初始化工作
  length_lexical = 0;
  omega_pointer = -1;
  hou_leng = 0;
  for(int i = 0; i<20;i++){
    lexical_expre[i].length = 0;
    struct_hou[i].calcu_length = 0;
    lexical_expre[i].logo  = 2; //默认为字符类型 
    struct_hou[i].logo = 2; //默认为字符类型 
  }
}
bool isDigit(char buffer){
  return buffer >= '0' && buffer <= '9';
}
bool isCalcu(char buffer){
  return buffer=='+' || buffer=='-'|| buffer=='*'|| buffer=='/'|| buffer=='^'|| buffer=='%';
}
bool input_string(){
  //输入中缀表达式
  int j=0;
  char ch;
  printf("Input such as 21+((42-2)*15+6)-18 or 21+(42-1)%%2 or 2^3 or -3+5*6:\n");
  while(true){
    ch = getchar();
    if(ch=='\n'){
        break;
    }
      user_string[j] = ch;
      j++;
    }
  printf("\n\n");
  printf("原来表达式：%s\n",user_string);
  for(int i=0; i<j; i++){
    ch = user_string[i];
    if(!(((ch<'9')&&(ch>'0'))||(ch=='+')||(ch=='*')||(ch=='\\')||(ch!=')')||(ch!='(')||(ch!='%')||(ch!='^')||(ch!='.'))){
      printf("输入了非法的字符！请重新输入！\n");
      return false;
    }
  }
  zhong_leng = j;
  return true; 
}

输入

21+((42-2)*15+6)-18

运行结果：

关于乘方优先级，输入

2^2^3

运行结果：

关于单目运算符以及小数，输入

-3+5*6.2

运行结果：

关于%和乘方混合运算，输入

-5+2^3%5

运行结果：

2.3.2 程序分析

1.首先包含了一些头文件，定义了一些全局变量和结构体。

2.input_string()函数用于接收用户输入的中缀表达式，并判断输入的合法性。

3.init()函数用于初始化一些变量和数据结构。

4.lexical_analysis()函数对输入的中缀表达式进行词法分析，将其转化为一个个的操作数和运算符，并存储在lexical_expre数组中。

5.translate()函数将中缀表达式转换为后缀表达式，即逆波兰表达式。它使用了两个栈：omega_stack用于存储运算符，struct_hou用于存储后缀表达式。

6.calculate()函数对后缀表达式进行计算。它遍历后缀表达式数组，并根据操作数和运算符进行相应的计算，结果存储在result结构体中。

7.主函数main()中的流程为：

调用input_string()函数接收用户输入的中缀表达式，直到输入正确为止。

调用init()函数进行初始化。

调用lexical_analysis()函数进行词法分析。

调用translate()函数将中缀表达式转换为后缀表达式。

输出后缀表达式。

调用calculate()函数计算后缀表达式，并输出计算结果。

程序主要由两部分组成，分别是中缀表达式转换为后缀表达式，计算后缀表达式。对于中缀表达式转换为后缀表达式主要由下面这段代码实现：

void translate(){ //将中缀表达式转换为后缀 
  int struct_point = 0;
  while(struct_point<length_lexical){ //当词法分析结果栈还有内容时
    struct Expression expre_trans = lexical_expre[struct_point];
    //omega_stack栈中只存储运算符
    if(strcmp(expre_trans.expre,"(")==0){
      //如果是左括号，直接入栈
      omega_stack[++omega_pointer] = '(';
    }
    else if(strcmp(expre_trans.expre,")")==0){
      //如果是右括号，则一直出栈，直到栈顶是左括号
      while(omega_stack[omega_pointer]!='('){
        struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
        hou_leng++;
        omega_pointer--;
      }
      omega_pointer--;
    }
    else if(strcmp(expre_trans.expre,"^")==0){
      omega_stack[++omega_pointer] = expre_trans.expre[0]; //如果是乘除取余符号，则expre_trans中的字符长度为1 
    }
    else if(strcmp(expre_trans.expre,"*")==0 || strcmp(expre_trans.expre,"/")==0||strcmp(expre_trans.expre,"%")==0){
      //如果是乘除符号和取余符号 
      //则把全部*/%符号都出栈（相当于：在左边的*/号的优先级比后面的*/的优先级高） 
      while(omega_stack[omega_pointer]=='*'||omega_stack[omega_pointer]=='/'||omega_stack[omega_pointer]=='%'||omega_stack[omega_pointer]=='^'){
        struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
        hou_leng++;
        omega_pointer--;
      }
      //将刚才的*/%号入栈
      omega_stack[++omega_pointer] = expre_trans.expre[0]; //进栈 
    }
    else if(strcmp(expre_trans.expre,"+")==0 || strcmp(expre_trans.expre,"-")==0){
      //如果是加减符号
      if(struct_point==0||(strcmp(lexical_expre[struct_point-1].expre,"(")==0)){
        //如果正负号在第一位，则说明是单目运算符 
        //如果加减符号的前一个符号为(，则说明是单目运算符。
        if(lexical_expre[struct_point+1].logo==0){ //如果下一个是整数 
          //如果是整数
          struct_hou[hou_leng].int_num =0-string_to_int(lexical_expre[struct_point+1].expre,lexical_expre[struct_point+1].length);
          struct_hou[hou_leng].logo = 0;
          hou_leng++;
        }
        else if(lexical_expre[struct_point+1].logo==1){ //如果下一个是浮点数 
          //如果是浮点数
          struct_hou[hou_leng].float_num =0-string_to_float(lexical_expre[struct_point+1].expre,lexical_expre[struct_point+1].length);
          struct_hou[hou_leng].logo = 1;
          hou_leng++;
        }
        else{
          printf("格式输入错误！\n");
          exit(0);
        }
        struct_point++;
      }
      else{
        //由于该+-号的优先级最低，只比(高，因此使所有栈中的字符都出栈，直至符号为(
        while(omega_pointer!=-1&&omega_stack[omega_pointer]!='('){
          struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
          hou_leng++;
          omega_pointer--;
        }
        //将新的加减符号入栈
        omega_stack[++omega_pointer] = expre_trans.expre[0]; //如果是加减符号，则expre_trans中的字符长度为1
      }
    }
    else{//非运算符 
      //说明是数字
      if(expre_trans.logo==0){
        //如果是整数
        struct_hou[hou_leng].int_num = string_to_int(expre_trans.expre,expre_trans.length);
        struct_hou[hou_leng].logo = 0;
        hou_leng++;
      }
      else{
        //如果是浮点数
        struct_hou[hou_leng].float_num = string_to_float(expre_trans.expre,expre_trans.length);
        struct_hou[hou_leng].logo = 1;
        hou_leng++;
      }
    }
    struct_point++;
  }
  while(omega_pointer!=-1){
    //当表达式扫描完毕后， 假如omage分析栈还存在元素，就依次全部加入到Polish栈中。 
    if(omega_stack[omega_pointer]!='('){
      struct_hou[hou_leng].calcu[struct_hou[hou_leng].calcu_length++] = omega_stack[omega_pointer];
      hou_leng++;
    }
    else{
      printf("输入的表达式错误！\n");
      exit(0);
    }
    omega_pointer--;
  }
}

程序解释：

1.定义了一个函数 translate()，没有返回值 (void)。

2.声明并初始化了一个变量 struct_point，表示词法分析结果栈的指针，初始值为0。

3.进入一个 while 循环，条件是 struct_point<length_lexical，即当词法分析结果栈还有内容时执行循环。

4.在循环中，从词法分析结果栈中取出一个元素，赋值给变量 expre_trans，它是一个结构体类型的变量，包含两个成员：expre 和 logo。

5.根据 expre_trans.expre 的不同取值，执行相应的操作：

如果是左括号 (，将其直接入栈 omega_stack，指针 omega_pointer 自增。

如果是右括号 )，则从栈顶开始将元素出栈，直到遇到左括号 (，期间将出栈的元素依次存入 struct_hou[hou_leng].calcu 数组中，同时更新 hou_leng 和 omega_pointer。

如果是乘除取余符号 ^，将其入栈 omega_stack，指针 omega_pointer 自增。

如果是乘除符号 *、/ 或 %，则将栈中所有 *、/、% 和 ^ 符号依次出栈，存入 struct_hou[hou_leng].calcu 数组中，然后将当前符号入栈 omega_stack，指针 omega_pointer 自增。

如果是加减符号 + 或 -，根据前一个字符判断是单目运算符还是双目运算符：

如果前一个字符是左括号 (，说明是单目运算符，再判断下一个字符的类型（整数或浮点数），将其负值存入 struct_hou[hou_leng] 对应的成员中，并更新 hou_leng。同时指针 struct_point 自增。

如果不是单目运算符，则将栈中所有字符依次出栈，存入 struct_hou[hou_leng].calcu 数组中，然后将当前符号入栈 omega_stack，指针 omega_pointer 自增。

如果是非运算符，则说明是数字，根据 expre_trans.logo 的值判断是整数还是浮点数，将其转换为对应类型后存入 struct_hou[hou_leng] 对应的成员中，并更新 hou_leng。

6.循环结束后，判断 omega_stack 是否还有剩余的元素：

如果有，从栈顶开始依次将元素出栈，如果出栈的元素不是左括号 (，则将其存入 struct_hou[hou_leng].calcu 数组中，并更新 hou_leng。

如果遇到左括号 (，说明输入的表达式有错误，输出错误信息并退出程序。

最后，指针 omega_pointer 自减。

通过循环遍历词法分析结果栈中的元素，并根据不同的操作符类型进行相应的处理。它利用两个栈 omega_stack 和 struct_hou 来实现中缀表达式到后缀表达式的转换。在转换过程中，遇到运算符时根据其优先级进行入栈和出栈操作，而遇到数字则直接存入输出结果数组中。最后，将栈中剩余的运算符依次出栈并存入输出结果数组中，得到转换后的后缀表达式。

对于后缀表达式的计算主要由下面这段代码实现：

void calculate(){ //计算后缀表达式 
  int struct_point = 0;
  while(struct_point<hou_leng){ //当逆波兰结果数组中还有内容时 
    struct Polish polish = struct_hou[struct_point];
    if (strcmp(polish.calcu,"+")==0){
      //如果是加号
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num+struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      //如果有一方是浮点数
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-1].float_num+temp;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = temp + struct_hou[struct_point-2].float_num;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num+struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"-")==0){
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num-struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = temp-struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num-temp;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num-struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"*")==0){
//      printf("进入乘号页面！\n");
      //如果是乘号 
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num*struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-1].float_num*temp;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = temp*struct_hou[struct_point-2].float_num;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num*struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
      else if (strcmp(polish.calcu,"^")==0){ 
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = pow(struct_hou[struct_point-2].float_num,struct_hou[struct_point-1].float_num);
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num = pow(struct_hou[struct_point-1].float_num,temp);
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = pow(temp,struct_hou[struct_point-2].float_num);
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = pow(struct_hou[struct_point-2].int_num,struct_hou[struct_point-1].int_num);
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"/")==0){
      if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==1){
        //如果都是浮点数
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num/struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==1&&struct_hou[struct_point-2].logo==0){
        //如果有一方是浮点数
        float temp = struct_hou[struct_point-2].int_num;
        struct_hou[struct_point].float_num =temp/struct_hou[struct_point-1].float_num;
        struct_hou[struct_point].logo=1;
      }
      else if(struct_hou[struct_point-1].logo==0&&struct_hou[struct_point-2].logo==1){
        float temp = struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].float_num = struct_hou[struct_point-2].float_num/temp;
        struct_hou[struct_point].logo=1;
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num/struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    else if (strcmp(polish.calcu,"%")==0){
      if(struct_hou[struct_point-1].logo==1||struct_hou[struct_point-2].logo==1){
        printf("浮点数不可以进行取整运算！\n");
        exit(0);
      }
      else{
        //如果都是整型 
        struct_hou[struct_point].int_num = struct_hou[struct_point-2].int_num % struct_hou[struct_point-1].int_num;
        struct_hou[struct_point].logo=0;
      }
    }
    if(polish.logo==2){
      for(int i = struct_point-2;  i<hou_leng-2; i++){
        struct_hou[i] = struct_hou[i+2];
      }
      struct_point = struct_point-2;
      hou_leng = hou_leng-2;
    }
    struct_point++;
  }
  result.float_num = struct_hou[0].float_num;
  result.int_num = struct_hou[0].int_num;
}

函数解释：

1.定义了一个变量 struct_point 用作遍历后缀表达式数组的索引。

2.进入 while 循环，条件是 struct_point 小于 hou_leng，即后缀表达式数组中还有内容需要计算。

3.在每次循环开始时，将当前索引 struct_point 处的元素赋值给变量 polish，该变量的类型是 struct Polish，其中包含了运算符和操作数。

4.使用 strcmp 函数比较 polish.calcu 和不同的运算符，根据不同的运算符类型执行相应的计算操作。

5.对于加法运算符 +，首先判断操作数的类型。如果两个操作数都是浮点数，则将它们相加并将结果存入 struct_hou[struct_point] 中，并将 logo 设置为 1 表示浮点数。如果其中一个操作数是浮点数，则将另一个操作数转换为浮点数后相加，并进行相同的处理。如果两个操作数都是整型，则将它们相加并将结果存入 struct_hou[struct_point] 中，并将 logo 设置为 0 表示整型。

6.对于减法运算符 -、乘法运算符 *、除法运算符 / 和取余运算符 %，逻辑类似于加法运算符的处理，只是采用不同的运算符进行相应的计算。

7.对于幂运算符 ^，通过调用 pow 函数计算两个操作数的幂，并进行相同的类型判断和处理。

8.在每个运算符的处理完成后，判断 polish.logo 是否为 2。如果是，则表示需要将计算结果与两个操作数在后缀表达式数组中的位置进行调整。具体操作是将后续元素向前移动两个位置，并相应地更新 struct_point 和 hou_leng。

9.最后，将计算结果存入全局变量 result 中的 float_num 或 int_num，具体根据结果的类型进行赋值。

该函数用于计算后缀表达式，并将结果存入全局变量中。它根据不同的运算符类型执行相应的计算操作，同时处理不同类型的操作数（浮点数和整型）。

2.4 实验心得

通过这次实验，我实现了逆波兰式的产生及计算代码，并对逆波兰式的原理和实现有了更加深入的理解。

逆波兰式通过将操作符放在操作数的后面来表示数学运算的顺序，避免了使用括号来确定运算的优先级。在实现程序过程中，关键是使用栈辅助转换中缀表达式为后缀表达式。在遍历中缀表达式的过程中，当遇到操作数时，直接输出；当遇到操作符时，与栈顶操作符比较优先级，如果当前操作符优先级较低，则将栈顶操作符输出，直到栈为空或栈顶操作符优先级较低。最后，将当前操作符入栈。通过遍历后缀表达式数组，根据不同的操作符和操作数类型，进行相应的计算操作。这部分代码涉及到浮点数和整型的判断和处理，以及各种运算符的计算规则。

在实验过程中，我发现逆波兰式的产生和计算代码紧密相连，两者相互依赖。逆波兰式的产生为逆波兰式的计算提供了基础，而逆波兰式的计算则是对逆波兰式生成算法的验证和应用。通过编写这两部分代码，我能够更加清晰地理解逆波兰式的工作原理，并能够熟练地处理逆波兰式的计算问题。

3. 致各位

一朝奋起鲲鹏翅，直上青云啸九天

【编译原理】逆波兰式的产生及计算：C/C++实现