当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 11 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : 一道C语言题,能者进!(面试题目)
帖子发表于 : 2007-03-13 8:51 

注册: 2007-02-05 22:02
帖子: 81
送出感谢: 0 次
接收感谢: 0 次
编写函数bool syntaxCheck(const char* s),功能是检查字符串s中的{和}、[和]、(和)是否匹配,即是否符合C语言的语法要求。


页首
 用户资料  
 
2 楼 
 文章标题 :
帖子发表于 : 2007-03-13 10:06 

注册: 2006-03-10 15:10
帖子: 3182
地址: xi'an China
送出感谢: 0 次
接收感谢: 2
你可以自己写,搞不清楚的细节可以和大家一块讨论

直接这样问,。。


最后由 dbzhang800 编辑于 2007-03-13 10:07,总共编辑了 1 次

页首
 用户资料  
 
3 楼 
 文章标题 :
帖子发表于 : 2007-03-13 10:06 
头像

注册: 2006-07-14 18:56
帖子: 345
地址: Apple Valley, Planet Tux, Linux System
送出感谢: 0 次
接收感谢: 0 次
代码:
#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;
}


页首
 用户资料  
 
4 楼 
 文章标题 :
帖子发表于 : 2007-03-15 0:40 

注册: 2005-09-26 14:51
帖子: 6
地址: Shaanxi xi'an
送出感谢: 0 次
接收感谢: 0 次
上面的程序有问题,比如对"[(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");
}


_________________
欢迎来我的个人主页:
http://huayanghao.googlepages.com/


页首
 用户资料  
 
5 楼 
 文章标题 :
帖子发表于 : 2007-03-15 5:29 
头像

注册: 2005-10-25 11:15
帖子: 1016
送出感谢: 0 次
接收感谢: 1
上面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表示符合语法,其他表示不符合。


_________________
hreiser@oakland:~$ killall -9 wife
police@oakland:~$ sudo find / -user hreiser
court@oakland:~$ sudo mv /home/hreiser /jail/
court@oakland:~$ sudo usermod -d /jail/hreiser -s "/usr/sbin/chroot /jail/" hreiser


页首
 用户资料  
 
6 楼 
 文章标题 :
帖子发表于 : 2007-03-15 12:42 

注册: 2005-09-26 14:51
帖子: 6
地址: Shaanxi xi'an
送出感谢: 0 次
接收感谢: 0 次
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表示符合语法,其他表示不符合。


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


_________________
欢迎来我的个人主页:
http://huayanghao.googlepages.com/


页首
 用户资料  
 
7 楼 
 文章标题 :
帖子发表于 : 2007-03-15 20:49 
头像

注册: 2005-10-25 11:15
帖子: 1016
送出感谢: 0 次
接收感谢: 1
huayanghao 写道:
sizeof 是跟系统位数无关的。

你弄错了。


_________________
hreiser@oakland:~$ killall -9 wife
police@oakland:~$ sudo find / -user hreiser
court@oakland:~$ sudo mv /home/hreiser /jail/
court@oakland:~$ sudo usermod -d /jail/hreiser -s "/usr/sbin/chroot /jail/" hreiser


页首
 用户资料  
 
8 楼 
 文章标题 :
帖子发表于 : 2007-03-18 0:43 

注册: 2005-09-26 14:51
帖子: 6
地址: Shaanxi xi'an
送出感谢: 0 次
接收感谢: 0 次
laborer 写道:
huayanghao 写道:
sizeof 是跟系统位数无关的。

你弄错了。


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


_________________
欢迎来我的个人主页:
http://huayanghao.googlepages.com/


页首
 用户资料  
 
9 楼 
 文章标题 :
帖子发表于 : 2007-03-18 2:57 
头像

注册: 2005-10-25 11:15
帖子: 1016
送出感谢: 0 次
接收感谢: 1
先心算一下下面这个程序结果,再用机器运行一下,看看一样不。

代码:
#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;
}


_________________
hreiser@oakland:~$ killall -9 wife
police@oakland:~$ sudo find / -user hreiser
court@oakland:~$ sudo mv /home/hreiser /jail/
court@oakland:~$ sudo usermod -d /jail/hreiser -s "/usr/sbin/chroot /jail/" hreiser


页首
 用户资料  
 
10 楼 
 文章标题 :
帖子发表于 : 2007-03-18 16:27 

注册: 2005-09-26 14:51
帖子: 6
地址: Shaanxi xi'an
送出感谢: 0 次
接收感谢: 0 次
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;
}

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


_________________
欢迎来我的个人主页:
http://huayanghao.googlepages.com/


页首
 用户资料  
 
11 楼 
 文章标题 :
帖子发表于 : 2007-03-20 10:34 

注册: 2007-03-20 9:33
帖子: 24
送出感谢: 0 次
接收感谢: 0 次
很简单的一道编译原理的问题嘛,
看过书了吗?


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 11 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 4 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译