尝试使用一堆字符串将反向抛光表示法转换为中缀,遇到一个小错误,我不知道是什么导致它

概述我已经实现了一个字符串堆栈,我正在尝试使用它将rpn转换为中缀.这是堆栈在中缀函数工作时的外观,例如,如果我输入2 3 5 – 8 *： 2 //push 22,3 //push 3(2+3) //reach operator, pop 2 and 3, format it, put result back on the stack 我已经实现了一个字符串堆栈,我正在尝试使用它将rpn转换为中缀.这是堆栈在中缀函数工作时的外观,例如,如果我输入2 3 5 – 8 *：

2             //push 22,3           //push 3(2+3)         //reach operator,pop 2 and 3,format it,put result back on the stack(2+3),5       //push 5((2+3)-5)     //reach operator,pop (2+3) and 5,put result back((2+3)-5),8   //push 8(((2+3)-5)*8) //reach operator,pop ((2+3)-5) and 8,format,put result back

遗憾的是,这不是该计划为我工作的方式,我认为它是技术性的,而不是我的算法.
输入“2 5 A”时,它有效,给出“(2 5)”的结果.尝试“40 50 A”,我得到“(40 50)”.但是,当尝试“50 100 A”时,我得到“()”.像“1 2 A 3 S”这样的更长的表达也给了我“( – )”.我似乎无法弄清楚造成这种情况的原因.请随意对它进行刺戳.这是我的代码：

#include <ctype.h>#include <stdio.h>#include <stdlib.h>#include <strings.h>#include <unistd.h>/*options to later implement (-e for evaluate,-c for infix conversion,-g for mock assembly */#define OP_EVAL "-e"#define OP_INFX "-c"#define OP_GENI "-g"/* begin stack of strings implementation */struct stack_entry {  char *data;  struct stack_entry *next;};struct stack_t{  struct stack_entry *head;  size_t stackSize;  };struct stack_t *newStack(voID){  struct stack_t *stack = malloc(sizeof *stack);  if (stack)    {      stack->head = NulL;      stack->stackSize = 0;    }  return stack;}char *copyString(char *str){  char *tmp = malloc(strlen(str) + 1);  if (tmp)    strcpy(tmp,str);  return tmp;}voID push(struct stack_t *theStack,char *value){  struct stack_entry *entry = malloc(sizeof *entry);   if (entry)    {      entry->data = copyString(value);      entry->next = theStack->head;      theStack->head = entry;      theStack->stackSize++;    }  else    {      printf("FAILURE\n");    }}char *top(struct stack_t *theStack){  if (theStack && theStack->head)    return theStack->head->data;  else    return NulL;}voID pop(struct stack_t *theStack){  if (theStack->head != NulL)    {      struct stack_entry *tmp = theStack->head;      theStack->head = theStack->head->next;      free(tmp->data);      free(tmp);      theStack->stackSize--;    }}/*end stack of strings implementation *//*begin argument handling for -c,-e and -g */enum method{  EVAL,INFX,GENI};int is_option(const char *str){  return (strcmp(str,OP_EVAL) == 0) ||         (strcmp(str,OP_INFX) == 0) ||         (strcmp(str,OP_GENI) == 0);}enum methodmanip_method(const char *arg){  if (strcmp(arg,OP_EVAL) == 0)    return EVAL;  else if (strcmp(arg,OP_INFX) == 0)    return INFX;  else if (strcmp(arg,OP_GENI) == 0)    return GENI;  else    return 0;}/* end of argument handling code (again,not even being used yet) *//* gets operator,converts it,if not A,S,X,D,or M returns NulL */char*get_oper(char *op){  if(strcmp(op,"A") == 0)    return "+";  if(strcmp(op,"S") == 0)    return "-";  if(strcmp(op,"X") == 0)    return "*";  if(strcmp(op,"D") == 0)    return "\";  if(strcmp(op,"M") == 0)    return "%";  else    return NulL;}/* formats an infix Expression */char* formats(char *s1,char *s2,char* op){  int length = strlen(s1) + strlen(s2) + strlen(op) + 3;  char *buf = malloc(length);  strcpy(buf,"(");  strcat(buf,s2);  strcat(buf,op);  strcat(buf,s1);  strcat(buf,")");  return buf;}/* 1) reads tokens and puts them on stack    2) when operator is reached,pops two elements off      the stack and formats it,then pushes the result onto the stack   3) after the loop ends,there should only be one element left on the      stack: the final infix Expression */char*infix(int argc,char *argv[],int x){  int i;  char *format,*result,*s1,*s2,*op;  struct stack_t *stack = newStack();  for(i = x; i < argc; i++){    if(!get_oper(argv[i])){      push(stack,argv[i]);    } else {      s1 = top(stack);      pop(stack);      s2 = top(stack);      pop(stack);      op = get_oper(argv[i]);      format = formats(s1,s2,op);      push(stack,format);    }  }  result = top(stack);  pop(stack);  return result;}intmain(int argc,char *argv[]){  char *result;  enum method method;  int x;  if (argc >= 4){    if (is_option(argv[1])){      if (argc < 5){    printf("not a valID calculatable Expression,exiting Now...\n");    exit (EXIT_FAILURE);      }      x = 2;      method = manip_method(argv[1]);    }    else {      x = 1;      method = EVAL;    }  } else {    printf("need option and or a valID reverse polish notation Expression,exiting Now...\n");    exit (EXIT_FAILURE);  }  result = infix(argc,argv,x);  printf("result: %s\n",result);  exit (EXIT_SUCCESS);}

编辑：这里有一些程序行为的例子

mesquite$rpcalc 1 5 Aresult: (1+5)mesquite$rpcalc 1 100 Sresult: (1-100)mesquite$rpcalc 1 2 A 3 Dresult: (\)mesquite$rpcalc 10 100 Mresult: (%)

解决方法 Bluepixy有它：当你d出元素时释放与堆栈相关的数据,所以这个：

s1 = top(stack);    // return handle to topmost itempop(stack);         // invalIDate that handle

是一个灾难的秘诀,特别是因为你的格式是malloc,这可能会让你有一个重新释放内存的句柄.字符串连接可能具有相同的源缓冲区和目标缓冲区.

因此,从pop中删除数据的释放(free(tmp-> data))并将其委托给调用者：

s1 = top(stack);pop(stack);if (s1 == NulL) exit(1);       //Stack underflows2 = top(stack);pop(stack);if (s2 == NulL) exit(1);       //Stack underflowop = get_oper(argv[i]);format = formats(s1,op);free(s1);free(s2);push(stack,format);

当然,您还必须释放最终结果：

result = infix(argc,x);printf("result: %s\n",result);free(result);

您当前的实施不能防止格式错误的表达(例如“A 2 3”,“1 2 A 3”,“12 A 44”).这些都发生在堆栈下溢(我试图在上面非常粗略地重复)或者在处理RN表达式后堆栈上有多个项目时.

你在评论中提到过BST,虽然我认为你的意思是AST.首先从rpn表达式创建语法树可能是个好主意.使用该表示,可以轻松生成中缀表示法,计算表达式并生成程序集.

这应该不会太困难,因为您的格式函数已经创建了一个树状结构 – 左节点,运算符,右节点 – 其中子节点或字符串max具有更多的子表达式.

总结

以上是内存溢出为你收集整理的尝试使用一堆字符串将反向抛光表示法转换为中缀,遇到一个小错误,我不知道是什么导致它全部内容，希望文章能够帮你解决尝试使用一堆字符串将反向抛光表示法转换为中缀,遇到一个小错误,我不知道是什么导致它所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。