4

我已经实现了一个字符串堆栈，我正在尝试使用它将 rpn 转换为中缀。这是中缀函数工作时堆栈的外观，例如，如果我输入2 3 + 5 - 8 *：

2             //push 2
2,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, format it, 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 method
manip_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;
}


int
main(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 A
result: (1+5)
mesquite$ rpcalc 1 100 S
result: (1-100)
mesquite$ rpcalc 1 2 A 3 D
result: (\)
mesquite$ rpcalc 10 100 M
result: (%)
4

1 回答 1

1

Bluepixy 有它：当您弹出元素时，您释放与堆栈关联的数据，因此：

s1 = top(stack);    // return handle to topmost item
pop(stack);         // invalidate that handle

是灾难的根源，特别是因为你malloc在formats，这很可能给你一个句柄来重新释放内存。您的字符串连接可能具有相同的源缓冲区和目标缓冲区。

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

s1 = top(stack);
pop(stack);
if (s1 == NULL) exit(1);       //Stack underflow

s2 = top(stack);
pop(stack);
if (s2 == NULL) exit(1);       //Stack underflow

op = get_oper(argv[i]);
format = formats(s1, s2, op);
free(s1);
free(s2);
push(stack, format);

当然，你还必须释放最终结果：

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

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

您在评论中提到了 BST，尽管我认为您的意思是 AST。首先从 RPN 表达式创建语法树可能是一个好主意。使用该表示，很容易生成中缀符号、评估表达式并生成程序集。

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

于 2015-05-09T05:47:14.783 回答