从C中的char数组中提取'（'和'）'内部的字符

Question

我被这个问题困住了：用户编写一个数学表达式，程序需要从中提取 ( ) ex 内的所有子表达式。 (x+2) 或 (x+(y-2))。

例如用户输入2-(5+(x-6)-(y+9))，程序应该return(x-6),(y+9), (5+(x-6)-(y+9))

这就是我尝试做的事情。

#include<stdio.h>
int main()
{
    char a[100];
    int i=0,t,j=0;
    printf("enter math expression:\n");
    while( (a[i++]=getchar()) != '\n' && i < 100);
    a[i] = '[=10=]';

  for (i=0; a[i]!='[=10=]'; i++)
    {
        if (a[i]=='(')
        {   printf("found (\n");
            j++;
              while (a[i] !=')')
                printf("%c",a[i++]);

                printf("%c",a[i]);

Answer 1

由于您正在处理嵌套表达式，因此您需要保留一个堆栈以便匹配括号。理想情况下，您应该在循环内：

每当找到 '(' 时，将字符串中的位置压入堆栈
找到“)”后，从堆栈中弹出匹配“(”的位置。您的表达式有开始和结束索引。
继续直到字符串完成

示例(x + (y+2))：

i == 0 -> '(' -> s.push(0);
i == 1 -> 'x' 
i == 2 -> '+'
i == 3 -> '(' -> s.push(3);
i == 4 -> 'y'
i == 5 -> '+'
i == 6 -> '2'
i == 7 -> ')' -> s.pop() [3, 7] contains '(y + 2)'
i == 8 -> ')' -> s.pop() [0, 8] contains '(x + (y+2))'

Answer 2

令 s 成为此上下文中的 cstring。

由于在有效的数学表达式中括号是平衡的，我们可以观察到，

s+1 是平衡的
如果 s[0] 是 '(' 那么我们就在括号表达式的开头。

在#1 的情况下，我们不关心第一个字符。因此，我们可以设置 s = s+1 并重新开始。在#2 的情况下，我们必须找到第一个字符的匹配结尾。所以，我们把它分成两部分。匹配的表达式和尾巴。两者都是有效的表达。所以，我们从头再来。

int main()
{
    char s[] = "2-(5+(x-6)-(y+9))";// s have to be modifiable.

    extractAndPrint(s, 0); // we are at start and 0 indicates balanced

    return 0;
}

现在，

void extractAndPrint(char *s, int found)
{
    if(s[0] == 0) return;//no more honey
    if(!found){ //so far balanced
        if(s[0] == '(') extractAndPrint(s+1, 1);// case 2
        else extractAndPrint(s+1, 0); //this is the case 1
    } else {//start of a expression
        char *t;
        //separates the end of current expression 
        //and the remaining part.
        mark_end(s, 0, &t);
        printf("(%s)\n", s);
        extractAndPrint(s, 0);//potentially contain more expression
        extractAndPrint(t, 0);//check past the previous exp
    }
}

我也喜欢这里的递归。这对我来说需要更少的思考。可以用更优雅的方式实现。

void mark_end(char *s, int c, char **t)
{
    if(c == 0){
        if(s[0] == ')'){
            *t = s+1;
            *s = '[=12=]';
        } else if(s[0] == '('){
            mark_end(s+1, c+1, t);
        } else {
            mark_end(s+1, c, t);
        }
    } else {
        if(s[0] == ')'){
            mark_end(s+1, c-1, t);
        } else if(s[0] == '('){
            mark_end(s+1, c+1, t);
        } else {
            mark_end(s+1, c, t);
        }
    }
}

输出：

(5+(x-6)-(y+9))
(x-6)
(y+9)

Answer 3

我推荐你使用状态机，在你的情况下这个状态机应该是合适的:

因此您的 main 将是一种开关盒，注意编写 pop 和 push 函数并用良好的结构表示您的堆

Answer 4

您应该使用递归将字符串解析为括号树。这是一个显示如何操作的示例：

#include <stdio.h>
#include <string.h>

#define MAX_DATA 100

int mathexp(const char *exp, int start, int end)
{
  int i = start;
  while(i < (start + end) && exp[i] != ')') {
    if(exp[i] == '(') {
      i = mathexp(exp, i + 1, end) + 1;
    } else {
      i++;
    }
  }
  char subexp[i - start];
  memcpy(subexp, &exp[start], i - start);
  subexp[i - start] = '[=10=]';
  printf("%s\n", subexp);
  return i;
}

int main(int argc, char *argv[])
{
  char input[MAX_DATA];
  printf("Enter a math expression: ");
  fgets(input, sizeof(input), stdin);
  input[strcspn(input, "\r\n")] = '[=10=]'; // remove trailing \r\n
  mathexp(input, 0, strlen(input));
  return 0;
}

当你测试它时，你有：

Enter a math expression: 2-(5+(x-6)-(y+9))
x-6
y+9
5+(x-6)-(y+9)
2-(5+(x-6)-(y+9))

从C中的char数组中提取'（'和'）'内部的字符

Extracting chars from inside '(' and ')' from char array in C

c

arrays

parsing

extract

char