一道C语言题，能者进！（面试题目）

[hlhl119]

编写函数bool syntaxCheck(const char* s)，功能是检查字符串s中的{和}、[和]、(和)是否匹配，即是否符合C语言的语法要求。

[dbzhang800]

你可以自己写，搞不清楚的细节可以和大家一块讨论

直接这样问，。。

[5451vs5451]

代码： 全选

#include <malloc.h>

typedef enum {
  false = 0,
  true = 1
} bool;

bool syntaxCheck(const char* s) {
  int i, j;
  char *stack = (char*)malloc(sizeof(s) / sizeof(s[0]));
  for (i = j = 0; s[i] != '\0'; i++) {
    switch (s[i]) {
    case '(':
    case '[':
    case '{':
      stack[j++] = s[i];
      break;
    case ')':
      if (j == 0 || s[--j] != '(') {
	free(stack);
	return false;
      }
      break;
    case ']':
      if (j == 0 || s[--j] != '[') {
	free(stack);
	return false;
      }
      break;
    case '}':
      if (j == 0 || s[--j] != '{') {
	free(stack);
	return false;
      }
      break;
    }
  }
  free(stack);
  return true;
}

[huayanghao]

上面的程序有问题，比如对"[(1+2)-1]*{8+(3*(9+6)+1)}"，检查结果就是错的。
这是常见的用stack的问题，可是你的stack根本就没用，你声明它干嘛？
改后如下所示：

代码： 全选

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

typedef enum {
  false = 0,
  true = 1
} bool;

bool SyntaxCheck(const char* s) {
  int i, j;
  char *stack = (char*)malloc(sizeof(s) / sizeof(s[0]));
  for (i = j = 0; s[i] != '\0'; i++) {
	switch (s[i]) {
	case '(':
	case '[':
	case '{':
	  stack[j++] = s[i];
	  break;
	case ')':
	  if (j == 0 || stack[--j] != '(') {
		free(stack);
		return false;
	  }
	  break;
	case ']':
	  if (j == 0 || stack[--j] != '[') {
		free(stack);
   return false;
	  }
	  break;
	case '}':
	  if (j == 0 || stack[--j] != '{') {
		free(stack);
		return false;
	  }
	  break;
	}
  }
  if (j==0){
	free(stack);
	return true;
  }
  else
	return false;
}

int main(int argc, char *argv[]) {
  printf("\n %s \n",argv[1]);
  if (SyntaxCheck(argv[1]))
	printf("\n True \n");
  else
	printf("\n False \n");
}

[laborer]

上面2位的这个用法是错的

代码： 全选

char *stack = (char*)malloc(sizeof(s) / sizeof(s[0]));

如果是32位系统，sizeof(指针)等于4，sizeof(char)等于1，这样malloc出来是4个byte，如果s中括号层数多，stack就要越界了。比较好的方法应该是

代码： 全选

char *stack = (char *)calloc(strlen(s), sizeof(char))

贴一个我写的解答

代码： 全选

int syntax_check(const char *s) {
    char *p;
    for (; *s != ')' && *s != ']' && *s != '}' && *s; s++) {
        if (*s == '(' || *s == '[' || *s == '{') {
            p = (char *)syntax_check(s + 1);
            if ((int)p == 0 || (int)p == 1 || *p != *s + (*s == '(' ? 1 : 2)) {
                return 1;
            }
            s = p;
        }
    }
    return *s ? (int)s : 0;
}

缺点是逻辑是反的，0表示符合语法，其他表示不符合。

[huayanghao]

上面2位的这个用法是错的

代码： 全选

char *stack = (char*)malloc(sizeof(s) / sizeof(s[0]));

如果是32位系统，sizeof(指针)等于4，sizeof(char)等于1，这样malloc出来是4个byte，如果s中括号层数多，stack就要越界了。比较好的方法应该是

代码： 全选

char *stack = (char *)calloc(strlen(s), sizeof(char))

贴一个我写的解答

代码： 全选

int syntax_check(const char *s) {
    char *p;
    for (; *s != ')' && *s != ']' && *s != '}' && *s; s++) {
        if (*s == '(' || *s == '[' || *s == '{') {
            p = (char *)syntax_check(s + 1);
            if ((int)p == 0 || (int)p == 1 || *p != *s + (*s == '(' ? 1 : 2)) {
                return 1;
            }
            s = p;
        }
    }
    return *s ? (int)s : 0;
}

缺点是逻辑是反的，0表示符合语法，其他表示不符合。

sizeof 是跟系统位数无关的。你可以自己写个程序看看sizeof('a')会不会是4个byte。

[laborer]

sizeof 是跟系统位数无关的。

你弄错了。

[huayanghao]

sizeof 是跟系统位数无关的。

你弄错了。

嗯，是我看错了，sizeof(pointer)对32位机的确是4,可是，对于上面的程序，sizeof(string)和sizeof(char)的确是跟系统平台无关的。上面的程序中并没有用到sizeof（pointer). 我觉得有一点你可能理解错了，就是sizeof(string)跟sizeof(pointer)是不一样的，虽然有时候用pointer[n]和string[n]可以达到一样的效果，但是用到sizeof中，他们是有区别的。

[laborer]

先心算一下下面这个程序结果，再用机器运行一下，看看一样不。

代码： 全选

#include <stdio.h>

int ptr_size(const char *s) {
    return sizeof(s);
}

int main() {
    char a[100] = "1234567890";
    char *b = "abcdefghij";
    char c[] = "klmnopqrst";
    printf("%s %s %s\n", a, b, c);
    printf("%d %d %d %d %d %d\n", 
           sizeof(a), sizeof(b), sizeof(c), 
           ptr_size(a), ptr_size(b), ptr_size(c));
    return 0;
}

[huayanghao]

先心算一下下面这个程序结果，再用机器运行一下，看看一样不。

代码： 全选

#include <stdio.h>

int ptr_size(const char *s) {
    return sizeof(s);
}

int main() {
    char a[100] = "1234567890";
    char *b = "abcdefghij";
    char c[] = "klmnopqrst";
    printf("%s %s %s\n", a, b, c);
    printf("%d %d %d %d %d %d\n", 
           sizeof(a), sizeof(b), sizeof(c), 
           ptr_size(a), ptr_size(b), ptr_size(c));
    return 0;
}

嗯，是我理解错你的意思了。上面那个程序确实有问题，因为传的pointer，所以在用sizeof时，分配的空间大小不对。只要在代码中改成 char *stack = (char*)malloc(strlen(s)); 就没问题了。

[kf701]

很简单的一道编译原理的问题嘛，
看过书了吗？