从C中的字符数组中从内部“(‘和’)”中提取字符

Question

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

例如，如果用户输入2- (5+ (x-6) - (y+9) )，程序应该返回(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] = '\0';

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

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

Answer 1

让，s是这个上下文中的一个cstring。

因为在有效的数学表达式中括号是平衡的，我们可以看到，

1. 如果s不是'(‘)，则s+1是平衡的。
2. 如果s是'(‘’，那么我们处于括号式表达式的开头。

在#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 = '\0';
        } 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 2

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

1. 每当发现'(‘’)时，将字符串中的位置推到堆栈中
2. 当找到')‘时，然后从堆栈中弹出匹配'(’)的位置。您有表达式的起始结束索引。
3. 继续，直到字符串完成

示例(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 3

我建议您使用状态机，在您的情况下，此状态机应该适合：

因此，您的主要功能将是一种开关情况，负责编写弹出函数和推送功能，并以良好的结构表示堆。