中缀、前缀和后缀表达式

发布于：

概念

通常，我们从小学开始接触到最常见的数学表达式，都是形如A * B或A + B * C之类的，即运算符/操作符在两个操作数的中间，这被称为中缀表达式（infix expression）。中缀表达式在处理A + B * C之类的表达式时，需要知道操作符+/*的优先级（precedence），然后才能根据优先级高低确定计算顺序。另外，括号也会影响计算顺序，计算机程序在解析中缀表达式时，确定计算顺序比较复杂，可以通过加括号来使得不需要知道各操作符的优先级就可以确定计算顺序。比如，有表达式A + B * C + D，可以被写成((A + (B * C)) + D)。

前缀表达式（prefix expression），又被称为波兰表达式（Polish expression），是因为它是波兰逻辑学家发明的一种记法。顾名思义，前缀表达式是把操作符放到操作数的前面，比如+ A B，意思是A与B进行+操作，也可以使用多个操作数，比如+ A B C，意思是A、B和C进行+操作。假如固定有且只有两个操作数，则括号省略时不影响计算顺序的判断，比如中缀表达式(A + B) * C可写成前缀表达式* (+ A B) C，因为操作符只能对两个操作数计算，所以括号是可以省略的，即* + A B C。

后缀表达式（postfix expression），又被称为逆波兰表达式（Reverse Polish expression），是为了与波兰表达式的叫法对应。后缀表达式是把操作符放到操作数的后面，比如A B +。

如无特殊说明，下面前缀与后缀表达式当中一个操作符的操作数均限制为两个

计算表达式

前缀与中缀表达式计算实现比后缀要复杂些。

下面的计算只针对加减乘除四个操作。

计算前缀表达式

使用栈来计算：

  1. 结构体EvalTuple，其有三个属性：char operator、double operand、int count，分别用来存储操作符、操作符作用的第一个操作数、操作数作用的操作数个数。
  2. 栈EvalTupleStack用来存储结构体EvalTuple。
  3. 合法的前缀表达式prefix_exp，其为字符串。
  4. 从左至右遍历prefix_exp，ch为遍历的当前字符串。
  5. 如果ch为空白字符串，则处理下一个字符。
  6. 如果ch为操作符（加减乘除），则创建一个EvalTuple类型结构体tuple。然后，tuple.operator值为ch，tuple->count值为0，并将tuple推入栈EvalTupleStack当中，然后处理下一个字符。
  7. 如果ch为其他，则从字符串prefix_exp当前索引开始往后匹配最长的合法数值,设其为num，设nextIndex为该数值后面字符的索引。对EvalTupleStack进行遍历：
  8. 如果为空，则中止遍历；
  9. 设top_tuple为EvalTupleStack最顶部的元素，如果top_tuple.count值为0，则top_tuple.operand值为num，top.count值为1，并中止遍历；如果top_tuple.count值不为0，则num值为top_tuple.operand与num进行top_tuple.operator计算后的结果，然后将top_tuple出栈，如果EvalTupleStack为空，则前缀表达式的计算结果result为num。
  10. 从nextIndex索引位置开始遍历prefix_exp。
  11. 遍历完成prefix_exp后，返回result。

下面使用 C 代码过程：

struct EvalTuple {
  char operator;
  double operand;
  int count;
};

double
prefix_eval(char *str) {
  char *cp = str;
  double result;
  Stack s = create_stack();

  while (*cp != '\0') {
    if (*cp == ' ') {
      cp++;
    } else if (*cp == '+' || *cp == '-' || *cp == '*' || *cp == '/') {
      EvalTupleType tuple;

      tuple = malloc(sizeof(struct EvalTuple));

      if (tuple == NULL) {
        perror("Out of memory!");
        exit(1);
      }

      tuple->operator = *cp;
      tuple->count = 0;
      push(s, tuple);
      cp++;
    } else {
      char *nextIndex;
      EvalTupleType top_tuple;
      double num = strtod(cp, &nextIndex);

      while(!is_empty(s)) {
        top_tuple = top(s);
        if (top_tuple->count == 1) {
          switch (top_tuple->operator) {
            case '+':
              num = top_tuple->operand + num;
              break;
            case '-':
              num = top_tuple->operand - num;
              break;
            case '*':
              num = top_tuple->operand * num;
              break;
            case '/':
              num = top_tuple->operand / num;
              break;
          }
          pop(s);
          if (is_empty(s)) {
            result = num;
          }
        } else {
          top_tuple->operand = num;
          top_tuple->count = 1;
          break;
        }
      }

      cp = nextIndex;
    }
  }

  return result;
}

计算后缀表达式

后缀表达式的计算很简单：

  1. 栈S，其元素为数值类型。
  2. 数值变量a、b，用于求值过程中。
  3. 将要求值的后缀表达式为postfix_exp，类型为字符串。
  4. 对postfix_exp从左至右进行遍历，当前遍历字符为ch:
  5. 如果ch为空白字符串，则直接遍历下一个字符；
  6. 如果ch为操作符（加减乘除），则对S进行出栈操作两次，取出的元素分别赋值给a和b。然后，根据ch对a和b进行运算，其计算结果推入栈S中，然后遍历下一个字符；
  7. 如果为其他，则从当前索引位置向后匹配最长的合法数值num，数值后面一位字符索引为nextIndex，将num推入栈S中，然后从索引nextIndex位置开始遍历。
  8. 遍历结束之后，返回S顶部的元素，即为最终计算结果。

下面是 C 代码过程：

double
postfix_eval(char *postfix_exp) {
  char *cp = postfix_exp;
  double a, b;
  double result;
  Stack s = create_stack();

  while (*cp != '\0') {
    if (*cp == ' ') {
      cp++;
    } else if (*cp == '+' || *cp == '-' || *cp == '*' || *cp == '/') {
      b = pop(s);
      a = pop(s);
      switch (*cp) {
        case '+':
          push(s, a + b);
          break;
        case '-':
          push(s, a - b);
          break;
        case '*':
          push(s, a * b);
          break;
        case '/':
          push(s, a / b);
          break;
      }
      cp++;
    } else {
      char *endp;
      push(s, strtod(cp, &endp));
      cp = endp;
    }
  }
  return pop(s);
}

参考

前缀中缀后缀栈