AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-02-01 159
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【编译原理】逆波兰式的产生及计算：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()中的流程为：

  1. 调用input_string()函数接收用户输入的中缀表达式，直到输入正确为止。
  2. 调用init()函数进行初始化。
  3. 调用lexical_analysis()函数进行词法分析。
  4. 调用translate()函数将中缀表达式转换为后缀表达式。
  5. 输出后缀表达式。
  6. 调用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 的不同取值，执行相应的操作：

  1. 如果是左括号 (，将其直接入栈 omega_stack，指针 omega_pointer 自增。
  2. 如果是右括号 )，则从栈顶开始将元素出栈，直到遇到左括号 (，期间将出栈的元素依次存入 struct_hou[hou_leng].calcu 数组中，同时更新 hou_leng 和 omega_pointer。
  3. 如果是乘除取余符号 ^，将其入栈 omega_stack，指针 omega_pointer 自增。
  4. 如果是乘除符号 *、/ 或 %，则将栈中所有 *、/、% 和 ^ 符号依次出栈，存入 struct_hou[hou_leng].calcu 数组中，然后将当前符号入栈 omega_stack，指针 omega_pointer 自增。
  5. 如果是加减符号 + 或 -，根据前一个字符判断是单目运算符还是双目运算符：
  6. 如果前一个字符是左括号 (，说明是单目运算符，再判断下一个字符的类型（整数或浮点数），将其负值存入 struct_hou[hou_leng] 对应的成员中，并更新 hou_leng。同时指针 struct_point 自增。
  7. 如果不是单目运算符，则将栈中所有字符依次出栈，存入 struct_hou[hou_leng].calcu 数组中，然后将当前符号入栈 omega_stack，指针 omega_pointer 自增。
  8. 如果是非运算符，则说明是数字，根据 expre_trans.logo 的值判断是整数还是浮点数，将其转换为对应类型后存入 struct_hou[hou_leng] 对应的成员中，并更新 hou_leng。

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

  1. 如果有，从栈顶开始依次将元素出栈，如果出栈的元素不是左括号 (，则将其存入 struct_hou[hou_leng].calcu 数组中，并更新 hou_leng。
  2. 如果遇到左括号 (，说明输入的表达式有错误，输出错误信息并退出程序。
  3. 最后，指针 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. 致各位

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

文章标签：
云数据库 ClickHouse
C++
自然语言处理
存储
编译器
算法
关键词：
C++计算
C++编译原理
编译原理C++
SarPro
目录
相关文章
hylreg
|
3月前
|
C++
C++ 根据程序运行的时间和cpu频率来计算在另外的cpu上运行所花的时间
C++ 根据程序运行的时间和cpu频率来计算在另外的cpu上运行所花的时间
hylreg
44 0
长梦
|
5月前
|
安全 编译器 C++
C++一分钟之-编译时计算：constexpr与模板元编程
【6月更文挑战第28天】在C++中，`constexpr`和模板元编程用于编译时计算，提升性能和类型安全。`constexpr`指示编译器在编译时计算函数或对象，而模板元编程通过模板生成类型依赖代码。常见问题包括误解constexpr函数限制和模板递归深度。解决策略包括理解规则、编写清晰代码、测试验证和适度使用。通过实战示例展示了如何使用`constexpr`计算阶乘和模板元编程计算平方。
长梦
92 13
hylreg
|
3月前
|
C++
C++ PCL 计算多个RT矩阵变换后的变换矩阵
C++ PCL 计算多个RT矩阵变换后的变换矩阵
hylreg
45 0
hylreg
|
3月前
|
C++
C++代码来计算一个点围绕另一个点旋转45度后的坐标
C++代码来计算一个点围绕另一个点旋转45度后的坐标
hylreg
79 0
嘟嘟嘟嘟嘟嘟
|
4月前
|
机器学习/深度学习 算法 C++
C++多态崩溃问题之为什么在计算梯度下降时需要除以批次大小（batch size）
C++多态崩溃问题之为什么在计算梯度下降时需要除以批次大小（batch size）
嘟嘟嘟嘟嘟嘟
51 1
长梦
|
4月前
|
C++ 开发者
C++一分钟之-编译时计算：constexpr与模板元编程
【7月更文挑战第2天】C++的`constexpr`和模板元编程（TMP）实现了编译时计算，增强代码效率。`constexpr`用于声明编译时常量表达式，适用于数组大小等。模板元编程则利用模板进行复杂计算。常见问题包括编译时间过长、可读性差。避免方法包括限制TMP使用，保持代码清晰。结合两者可以解决复杂问题，但需明确各自适用场景。正确使用能提升代码性能，但需平衡复杂性和编译成本。
长梦
128 3
爱喝兽奶的熊孩子
|
5月前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
63 2
爱喝兽奶的熊孩子
|
5月前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
89 2
67vpym2vvkfhs
|
5月前
|
存储 编译器 C++
详细解读C++编译原理
详细解读C++编译原理
67vpym2vvkfhs
35 0
吐个泡泡。。。。
|
6月前
|
测试技术 C++
C++|运算符重载（3）|日期类的计算
C++|运算符重载（3）|日期类的计算
吐个泡泡。。。。
35 0

热门文章

最新文章

  • 1
    2015级C++第10、11周补充实践项目 继承和派生
  • 2
    C++智能指针(auto_ptr)详解
  • 3
    C++第1周项目2——日期结构体
  • 4
    C++11中的tuple应用：让函数返回多个值
  • 5
    C++中消息自动派发之一 About JSON
  • 6
    读书笔记 effective c++ Item 53 关注编译器发出的警告
  • 7
    【C++ 常见的异步机制】探索现代异步编程：从 ASIO 到协程的底层机制解析
  • 8
    【C/C++ OCR识别】深入探索：Qt C++与OCR识别的完美结合
  • 9
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 10
    《Effective C++》item25：考虑写出一个不抛异常的swap函数
  • 1
    C++|多态性与虚函数（1）功能绑定|向上转换类型|虚函数
    48
  • 2
    C++|运算符重载（1）|为什么要进行运算符重载
    50
  • 3
    C++入门（命名空间）
    45
  • 4
    C++ delete语句
    42
  • 5
    c++ 创建对象
    39
  • 6
    C++ string类
    46
  • 7
    车辆管理系统设计（C++）
    57
  • 8
    通过C++和libcurl下载网易云音乐音频文件的5个简单步骤
    87
  • 9
    消除游戏（第十三届蓝桥杯省赛C++C组 , 第十三届蓝桥杯省赛PythonA/B/研究生组）
    65
  • 10
    三国游戏（第十四届蓝桥杯省赛C++C组）
    53

    • 相关课程

    更多
  • C++ 入门教程开发文档
  • 从 0 入门函数计算
  • 机器学习入门-概念原理及常用算法
  • C语言学习教程
  • 你的第一门C语言课
  • Java面向对象编程

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    阿里云OSS设置跨域访问