aboutsummaryrefslogtreecommitdiff
path: root/reverse_substr_parentheses.c
blob: e2103b656af976545f8f7b4fdf487ee7cd3c8228 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 1190. Reverse Substrings Between Each Pair of Parentheses
#include "leetcode.h"

/*
 * you are given a string 's' that consists of lower case english letters and
 * brackets. reverse the strings in each pair of matching parentheses, starting
 * from the innermost one. your result should not contain any brackets.
 */

struct node {
  int index;
  struct node *next;
};

void qpush(struct node **top, int idx) {
  struct node *n = (struct node *)malloc(sizeof(struct node));
  n->index = idx;
  n->next = NULL;
  if (!(*top)) {
    *top = n;
    return;
  }
  n->next = *top;
  *top = n;
  return;
}

int qpop(struct node **top) {
  if (!(*top))
    return 0;
  int x = (*top)->index;
  *top = (*top)->next;
  return x;
}

char *reverseParentheses(char *s) {
  if (!s)
    return "";
  struct node *top = NULL;
  for (int i = 0; i < strlen(s); i++) {
    if (s[i] == '(')
      qpush(&top, i);
    else if (s[i] == ')') {
      int beg = qpop(&top), end = i - 1;
      s[beg] = ' ';
      beg++;
      while (beg < end) {
        char c = s[beg];
        s[beg] = s[end];
        s[end] = c;
        beg++, end--;
      }
      s[i] = ' ';
    }
  }
  int j = 0;
  for (int i = 0; i < strlen(s); i++)
    if (s[i] != ' ')
      s[j++] = s[i];
  s[j] = '\0';
  return s;
}

int main() {
  char s1[] = "(abcd)", s2[] = "(u(love)i)", s3[] = "(ed(et(oc))el)";
  printf("%s\n", reverseParentheses(s1)); // expect: dcba
  printf("%s\n", reverseParentheses(s2)); // expect: iloveu
  printf("%s\n", reverseParentheses(s3)); // expect: leetcode
}