fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <assert.h>
  5.  
  6. #define MAX_NODE_SIZE 128
  7.  
  8. typedef struct node {
  9.   char data;
  10.   struct node *next;
  11. } Node;
  12.  
  13. typedef struct {
  14.   Node *head;
  15.   Node *crnt;
  16. } List;
  17.  
  18. typedef struct {
  19.   int max;
  20.   int num;
  21.   List stk;
  22. } Stack;
  23.  
  24. #define head(stack) ((stack)->stk.head)
  25. #define crnt(stack) ((stack)->stk.crnt)
  26. #define num(stack) ((stack)->num)
  27.  
  28. static char pop(Stack *stack)
  29. {
  30.   char data = crnt(stack)->data;
  31.   Node *next = crnt(stack)->next;
  32.  
  33.   free(crnt(stack));
  34.   crnt(stack) = next;
  35.   num(stack)--;
  36.  
  37.   return data;
  38. }
  39.  
  40. static void final(Stack *stack)
  41. {
  42.   while (crnt(stack) != head(stack)) {
  43.     Node *next = crnt(stack)->next;
  44.     free(crnt(stack));
  45.     crnt(stack) = next;
  46.   }
  47. }
  48.  
  49. static void push(Stack *stack, char data)
  50. {
  51.   Node *node;
  52.  
  53.   if (stack->num + 1 >= stack->max) {
  54.     fprintf(stderr, "stack size is overflow, which must be smaller than %d\n", stack->max);
  55.     final(stack);
  56.     exit(1);
  57.   }
  58.  
  59.   node = calloc(1, sizeof(*node));
  60.   if (node == NULL) {
  61.     fprintf(stderr, "Cannot allocate memory (stack size = %d)\n", stack->num);
  62.     final(stack);
  63.     exit(1);
  64.   }
  65.  
  66.   node->data = data;
  67.   node->next = crnt(stack);
  68.   crnt(stack) = node;
  69.   num(stack)++;
  70. }
  71.  
  72. static void dbg(Stack *stack)
  73. {
  74.   Node *node;
  75.  
  76.   printf("max = %d\n", stack->max);
  77.   printf("num = %d\n", num(stack));
  78.  
  79.   for (node = crnt(stack); node != head(stack); node = node->next)
  80.     printf("%c\n", node->data);
  81. }
  82.  
  83. static void init(Stack *stack, Node *head)
  84. {
  85.   stack->max = MAX_NODE_SIZE;
  86.   stack->num = 0;
  87.   head(stack) = head;
  88.   crnt(stack) = head;
  89. }
  90.  
  91. #define valid_or_return(stack, str, c, p)                            \
  92. do {                                                                 \
  93.   if (num(stack) == 0 || pop(stack) != c) {                          \
  94.     printf("%s is invalid. %c is invalid character.\n", str, *p);    \
  95.     final(stack);                                                    \
  96.     return;                                                          \
  97.   }                                                                  \
  98. } while (0)
  99.  
  100. static void validate(char *str)
  101. {
  102.   Stack stack;
  103.   Node head;
  104.   char *p;
  105.  
  106.   init(&stack, &head);
  107.  
  108.   for (p = str; *p != '\0'; p++) {
  109.     /** FIXME: not smart switch statement */
  110.     switch (*p) {
  111.     case '(':
  112.     case '{':
  113.     case '[':
  114.       push(&stack, *p);
  115.       break;
  116.     case ')':
  117.       valid_or_return(&stack, str, '(', p);
  118.       break;
  119.     case '}':
  120.       valid_or_return(&stack, str, '{', p);
  121.       break;
  122.     case ']':
  123.       valid_or_return(&stack, str, '[', p);
  124.       break;
  125.     default:
  126.       /** skip this character */
  127.       break;
  128.     }
  129.   }
  130.  
  131.   if (num(&stack) == 0)
  132.     printf("%s is valid.\n", str);
  133.   else
  134.     printf("%s is invalid.\n", str);
  135.  
  136.   final(&stack);
  137. }
  138.  
  139. static void task1()
  140. {
  141.   Stack stack;
  142.   Node head;
  143.  
  144.   printf("task1\n");
  145.  
  146.   init(&stack, &head);
  147.  
  148.   push(&stack, 'A');
  149.   push(&stack, 'B');
  150.   push(&stack, 'C');
  151.   push(&stack, 'C');
  152.   pop(&stack);
  153.   pop(&stack);
  154.   dbg(&stack);
  155.  
  156.   /**
  157.   do {
  158.     int i;
  159.     for (i = 0; i < stack.max; i++)
  160.       push(&stack, '0');
  161.   } while (0);
  162.   */
  163.  
  164.   final(&stack);
  165. }
  166.  
  167. static void task2()
  168. {
  169.   printf("task2\n");
  170.  
  171.   validate("(a)");
  172.   validate("[a(b)c]");
  173.   validate("{a(b)cd}");
  174.   validate("{e}");
  175.   validate("(a}");
  176.   validate("[a(bc]");
  177.   validate("{a(b)cd}[e}");
  178.   validate("({}[()])");
  179.   validate("({])");
  180.   validate("({})])");
  181.   validate("({}[()");
  182. }
  183.  
  184. int main(void)
  185. {
  186.   task1();
  187.   task2();
  188.   return 0;
  189. }
  190.  
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
task1
max = 128
num = 2
B
A
task2
(a) is valid.
[a(b)c] is valid.
{a(b)cd} is valid.
{e} is valid.
(a} is invalid. } is invalid character.
[a(bc] is invalid. ] is invalid character.
{a(b)cd}[e} is invalid. } is invalid character.
({}[()]) is valid.
({]) is invalid. ] is invalid character.
({})]) is invalid. ] is invalid character.
({}[() is invalid.
https://ideone.com/7UwiWH
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!