4
\$\begingroup\$

I'm a C++ programmer using SPOJ problems to learn C(99). This is my solution to the problem CMEXPR, where the goal is to read a valid expression (+, -, *, / only) from input and write it on output with superfluous parentheses removed.

The code yields correct answer according to the online judge (got an AC). My question is whether there are any C++-isms in the code and if so, what would be a more idiomatic C way of expressing them. Basically, I don't want to write C++ code in C (just like I don't like C code written in C++).

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>


//#define TESTING

#ifdef TESTING
  #define TEST_ASSERT(maCond) do { if (!(maCond)) { printf("%d: %s\n", __LINE__, #maCond); exit(1); } } while (0)
  #define TEST_ASSERT_MSG(maCond, maFormat, maMsg) \
    do { \
      if (!(maCond)) { printf("%d: %s: '" maFormat "'\n", __LINE__, #maCond, (maMsg)); exit(1); } \
    } while (0)
  #define IF_TESTING(...) __VA_ARGS__
#else
  #define TEST_ASSERT(maCond) do {} while (0)
  #define TEST_ASSERT_MSG(maCond, maFormat, maMsg) do {} while(0)
  #define IF_TESTING(...)
#endif


enum ParsingContext
{
  CONTEXT_FIRST_TERM
  , CONTEXT_ADDITIVE_EXPRESSION
  , CONTEXT_NONFIRST_TERM
};


struct ExprNode
{
  char type;
  struct ExprNode *child[2];
};


struct NodeMemory
{
  struct ExprNode data[MAX_NODE_COUNT];
  struct ExprNode *end;
};


struct ExprNode* createNode(struct NodeMemory *mem, char type)
{
  struct ExprNode *node = mem->end++;
  TEST_ASSERT(mem->end - mem->data <= MAX_NODE_COUNT);
  node->type = type;
  IF_TESTING(
    node->child[0] = node->child[1] = NULL;
  )
  return node;
}


struct ExprNode* moveToChild(
  struct NodeMemory * restrict mem
  , struct ExprNode * restrict node
  , size_t idxChild
  , char newParentType
)
{
  struct ExprNode * result = createNode(mem, newParentType);
  result->child[idxChild] = node;
  return result;
}


char readChar(const char * restrict * restrict in)
{
  char c = **in;
  ++*in;
  return c;
}


void writeChar(char * restrict * restrict out, char c)
{
  **out = c;
  ++*out;
}


struct ExprNode* parse(
  struct NodeMemory * restrict mem
  , const char * restrict * restrict in
  , struct ExprNode * restrict root
  , enum ParsingContext context
)
{
  TEST_ASSERT(root != NULL);
  bool skipStart = (context == CONTEXT_NONFIRST_TERM);
  // Left operand
  if (!skipStart) {
    switch (**in) {
      case '(':
        ++*in;
        root = parse(mem, in, root, CONTEXT_FIRST_TERM);
        TEST_ASSERT_MSG(**in == ')', "%c", **in);
        ++*in;
        break;
      default:
        TEST_ASSERT_MSG(
          **in != ')'
          && **in != '+'
          && **in != '-'
          && **in != '*'
          && **in != '/'
          && **in != '\n'
          , "%c", **in
        );
        root->type = readChar(in);
        break;
    }
  }
  for (;;) {
    // Operator
    if (!skipStart) {
      switch (**in) {
        case '\n':
        case ')':
          TEST_ASSERT(root != NULL);
          TEST_ASSERT(root->type != '.');
          return root;
        case '+':
        case '-':
          if (context == CONTEXT_NONFIRST_TERM) {
            TEST_ASSERT(root != NULL);
            TEST_ASSERT(root->type != '.');
            return root;
          }
          TEST_ASSERT(
            (context == CONTEXT_ADDITIVE_EXPRESSION)
            ==
            (root->type == '+' || root->type == '-')
          );
          context = CONTEXT_ADDITIVE_EXPRESSION;
          root = moveToChild(mem, root, 0, readChar(in));
          break;
        case '*':
        case '/':
          if (context == CONTEXT_ADDITIVE_EXPRESSION) {
            TEST_ASSERT(root->child[1]->type != '.');
            root->child[1] = moveToChild(mem, root->child[1], 0, readChar(in));
            root->child[1] = parse(mem, in, root->child[1], CONTEXT_NONFIRST_TERM);
            continue; // Parsed up to next operator or teminator
          }
          root = moveToChild(mem, root, 0, readChar(in));
          break;
        default:
          TEST_ASSERT(false);
          break;
      }
    }
    skipStart = false;
    // Right operand
    switch (**in) {
      case '(':
        ++*in;
        root->child[1] = parse(mem, in, createNode(mem, '.'), CONTEXT_FIRST_TERM);
        TEST_ASSERT_MSG(**in == ')', "%c", **in);
        ++*in;
        break;
      default:
        TEST_ASSERT_MSG(
          **in != ')'
          && **in != '+'
          && **in != '-'
          && **in != '*'
          && **in != '/'
          && **in != '\n'
          , "%c", **in
        );
        root->child[1] = createNode(mem, readChar(in));
        break;
    }
  }
}


void serialiseTree(const struct ExprNode * restrict node, char * restrict * restrict out, char parentType, bool isLeftChild)
{
  IF_TESTING(
    if (!node) {
      writeChar(out, 'N');
      return;
    }
  )
  TEST_ASSERT(
    parentType == '+'
    || parentType == '-'
    || parentType == '*'
    || parentType == '/'
  );
  bool paren = false;
  switch (node->type) {
    case '+':
    case '-':
      paren = (
        parentType == '*'
        || parentType == '/'
        || (parentType == '-' && !isLeftChild)
      );
      break;
    case '*':
    case '/':
      paren = (parentType == '/' && !isLeftChild);
      break;
    default:
      writeChar(out, node->type);
      return;
  }
  if (paren) {
    writeChar(out, '(');
  }
  serialiseTree(node->child[0], out, node->type, true);
  writeChar(out, node->type);
  serialiseTree(node->child[1], out, node->type, false);
  if (paren) {
    writeChar(out, ')');
  }
}


void createTree(struct NodeMemory *mem)
{
  char expr[MAX_INPUT_SIZE + 2];
  fgets(expr, sizeof(expr), stdin);
  const char *in = expr;
  if (*in == '\n') {
    fputs(expr, stdout);
    return;
  }
  struct ExprNode *root = parse(mem, &in, createNode(mem, '.'), CONTEXT_FIRST_TERM);
  TEST_ASSERT(*in == '\n');
  TEST_ASSERT(root != NULL);
  char *out = expr;
  serialiseTree(root, &out, '+', true);
  *out++ = '\n';
  *out = 0;
  TEST_ASSERT(out - expr < sizeof(expr));
  fputs(expr, stdout);
}


void runCase(void)
{
  struct NodeMemory mem;
  mem.end = mem.data;
  createTree(&mem);
}


int main(void) {
  int caseCount;
  fscanf(stdin, "%d\n", &caseCount);
  for (int idxCase = 0; idxCase < caseCount; ++idxCase) {
    runCase();
  }
  return 0;
}

Notes:

  • I use ideone for developing this code, so that's why I'm using my own assertions instead of built-in assert(); an "unusual termination" wouldn't be too helpful.

  • There's no error checking on input because in the context of the online judge, input correctness is guaranteed.

  • NodeMemory is used to avoid overhead of dynamic allocation in presence of a known maximum problem size.

\$\endgroup\$
3
\$\begingroup\$

These comments are not really related to writing "idiomatic C", merely things I noticed in your code.

  • Your handling of commas in lists is odd:

    enum ParsingContext {
        CONTEXT_FIRST_TERM
        , CONTEXT_ADDITIVE_EXPRESSION
        , CONTEXT_NONFIRST_TERM
    };
    
    struct ExprNode* moveToChild(
        struct NodeMemory * restrict mem
        , struct ExprNode * restrict node
        , size_t idxChild
        , char newParentType
        )
    

    I have never seen things written like that and don't see any advantage over the normal use:

    enum ParsingContext {
        CONTEXT_FIRST_TERM,
        CONTEXT_ADDITIVE_EXPRESSION,
        CONTEXT_NONFIRST_TERM
    };
    
    struct ExprNode* moveToChild(struct NodeMemory * restrict mem,
                                 struct ExprNode * restrict node,
                                 size_t idxChild,
                                 char newParentType)
    
  • Your macros and their invocation should allow a semicolon to be placed where expected. Otherwise, syntax-aware editors can get confused and mess up the indentation:

        IF_TESTING(
            node->child[0] = node->child[1] = NULL;
            )
            return node;
    

    Better to move the ; out of the bracket:

        IF_TESTING((node->child[0] = node->child[1] = NULL));
        return node;
    
  • Your asserts that check against a list of chars could be simpler with strchr (also I find the placement of the && here to be distracting, but I know some people like it that way):

    TEST_ASSERT_MSG(
       **in != ')'
       && **in != '+'
       && **in != '-'
       && **in != '*'
       && **in != '/'
       && **in != '\n'
       , "%c", **in
       );
    

    Neater (?):

    TEST_ASSERT_MSG(!strchr(")+-*/\n", **in), "%c", **in);
    
  • I always find passing double pointers to be awkward and confusing, so I avoid it if possible. In this case it seems that you could read and write the input/output string directly to/from stdin/out as you go, replace readChar and writeChar with fgetc and fputc and pass stdin/stdout around in instead of in and out (or just use the stdin/stdout globals).

  • Note that using an assert to check for exceeding the available memory is incorrect. This should be an explicit if and exit.

    TEST_ASSERT(mem->end - mem->data <= MAX_NODE_COUNT);
    
\$\endgroup\$
4
  • \$\begingroup\$ +1, thanks. Nice use of strchr(), wouldn't have thought about that. The out-of-memory assert is due to the SPOJ specifics - I know the maximum input size, so running out of space can only be a bug in the algorithm. As for the , and &&, I find list modifications usually happen at the end more than at the beginning, and this placement makes the last line syntax non-special. \$\endgroup\$ Oct 2 '13 at 20:53
  • \$\begingroup\$ About per-character input; wouldn't that be noticably slower than reading the string at once and then parsing it? \$\endgroup\$ Oct 2 '13 at 20:53
  • \$\begingroup\$ With your , and && isn't the first line syntax now "special" (ie. it doesn't have a , etc)? Per-char reading speed noticeable to whom? Unless you are operating on really huge input strings I doubt the speed difference will be noticeable to a user. \$\endgroup\$ Oct 2 '13 at 22:26
  • \$\begingroup\$ Yes, the first line is special. But as I said, experience tells me one modifies a list's end more often than its beginning (adding params etc.). Per-char: it's true that on 250-char strings (even if there are tens of thousands of them), I was probably overly cautious. Thanks again. \$\endgroup\$ Oct 3 '13 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.