c - 解析数学表达式字符串

Question

所以这是我的问题，我必须创建一个程序来实现 shunting yard algorithm在 C 中。 为此，我首先需要将给定的数学表达式解析为它的组成部分。所以我认为对给定字符串进行简单的 for 循环就可以解决问题。

char *math_exp = "2 + 4";
for (int i = 0; (unsigned) i < strlen(math_expr); i++) {
    printf("%c", math_expr[i]);
}

> 2 + 4

但是当字符串包含的数字位数多于 1 时，这很快就会遇到问题。

for (int i = 0; (unsigned) i < strlen(math_expr); i++) {
    // skip if char is a space
    if ((int) math_expr[i] == 32) {
        continue;
    }
    printf("%c ", math_expr[i]);
}
> 2 2 + 4

22 现在被视为两个单独的数字。因此，我尝试通过使用分隔符 SPACE 拆分字符串来遍历字符串中的所有标记。

char math_expr[] = "22 + 4";
char *token = strtok(math_expr, " ");

while (token != NULL) {
    printf("%s ", token);
    token = strtok(NULL, " ");
}
> 22 + 4

这似乎可行，但很快就遇到了当表达式中有括号时该怎么做的问题。例如:

char math_expr[] = "(22 + 2)";
char *token = strtok(math_expr, " ");

while (token != NULL) {
    printf("%s\n", token);
    token = strtok(NULL, " ");
}
> (22
> +
> 2)

现在我卡住了，有没有办法绕过这个问题？我需要能够提取每个运算符和数字(包括所有可能的数字)，此外我还需要能够区分括号和它们所附加的数字。我希望有一些简单的方法可以做到这一点。感谢任何帮助。

Answer 1

Tokenization是句法分析的第一步。因此，将它封装到一个抽象层中可能是个好主意，一个一次产生一个标记的函数。此函数还丢弃空格并将连续的数字组合成数字。很难将这些步骤委托(delegate)给 strtok()。最后，该函数可能会将单个字符重新包装成更结构化的信息。

#include <ctype.h>
#include <stdio.h>

#define T_NUMBER 0
#define T_OPERATOR 1
#define T_BRACKET 2

typedef struct {
  int type;
  int value;
} token;

/* Reads the next token from stdin. Returns 1 on success, 0 on EOL. */
int next_token(token *t) {
  char c;

  /* discard spaces silently */
  do {
    c = getchar();
  } while (c == ' ');

  if (isdigit(c)) {
    t->type = T_NUMBER;
    t->value = 0;
    do {
      t->value = t->value * 10 + (c - '0');
      c = getchar();
    } while (isdigit(c));
    ungetc(c, stdin); /* save the non-digit for next time */

  } else if (c == '+' || c == '-' || c == '*' || c == '/') {
    t->type = T_OPERATOR;
    t->value = c;

  } else if (c == '(' || c == ')') {
    t->type = T_BRACKET;
    t->value = c;

  } else if (c == '\n') {
    ungetc(c, stdin); /* make sure we always return 0 from now on */
    return 0;

  } else {
    /* handle illegal character */

  }

  return 1;
}

int main() {

  token t;

  while (next_token(&t)) {
    switch (t.type) {
      case T_NUMBER:   printf("number   %d\n", t.value); break;
      case T_OPERATOR: printf("operator %c\n", t.value); break;
      case T_BRACKET:  printf("bracket  %c\n", t.value); break;
    }
  }

  return 0;
}

样本运行:

(22+   37 * ( 1534-9)) + 18
bracket  (
number   22
operator +
number   37
operator *
bracket  (
number   1534
operator -
number   9
bracket  )
bracket  )
operator +
number   18