First commitHEADmaster

Signed-off-by: Mattias Andrée <m@maandree.se>

1 files changed, 180 insertions, 0 deletions

diff --git a/binary-tree.c b/binary-tree.c
new file mode 100644
index 0000000..c43f59e
--- /dev/null
+++ b/binary-tree.c
@@ -0,0 +1,180 @@
+/* See LICENSE file for copyright and license details. */
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#if defined(__GNUC__)
+# pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
+# pragma GCC diagnostic ignored "-Wsuggest-attribute=pure"
+#endif
+
+
+static char **tokens;
+static size_t ntokens;
+
+
+struct node {
+	int is_operand;
+	const char *symbol;
+	struct node *left;
+	struct node *right;
+};
+
+
+static struct node *
+operand_node(const char *token)
+{
+	struct node *ret = malloc(sizeof(*ret));
+	ret->is_operand = 1;
+	ret->symbol = token;
+	ret->left = NULL;
+	ret->right = NULL;
+	return ret;
+}
+
+
+static struct node *
+operator_node(struct node *left, const char *operator, struct node *right)
+{
+	struct node *ret = malloc(sizeof(*ret));
+	ret->is_operand = 0;
+	ret->symbol = operator;
+	ret->left = left;
+	ret->right = right;
+	return ret;
+}
+
+
+static void
+print_node(struct node *node)
+{
+	if (node->is_operand) {
+		printf("%s", node->symbol);
+	} else {
+		printf("(");
+		print_node(node->left);
+		printf(" %s ", node->symbol);
+		print_node(node->right);
+		printf(")");
+	}
+}
+
+
+static const char *
+next_token(void)
+{
+	static size_t token_i = 0;
+	return token_i == ntokens ? NULL : tokens[token_i++];
+}
+
+
+static struct node *
+parse_operand(void)
+{
+	const char *token = next_token();
+	if (!token)
+		exit(2); /* syntax error */
+	return operand_node(token);
+}
+
+
+static int
+get_precedence(const char *token, int *ltr)
+{
+	int prec = 0;
+	*ltr = 1;
+	if (!strcmp(token, ","))
+		return prec;
+	prec++;
+	*ltr = 0;
+	if (!strcmp(token, "=") || !strcmp(token, "+=") || !strcmp(token, "-=") || !strcmp(token, "*=") ||
+	    !strcmp(token, "%=")  || !strcmp(token, "<<=") || !strcmp(token, ">>=") || !strcmp(token, "&=") ||
+	    !strcmp(token, "^=")  || !strcmp(token, "|="))
+		return prec;
+	prec++;
+	*ltr = 1;
+	if (!strcmp(token, "||"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "&&"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "|"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "^"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "&"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "==") || !strcmp(token, "!="))
+		return prec;
+	prec++;
+	if (!strcmp(token, "<=") || !strcmp(token, "<") || !strcmp(token, ">=") || !strcmp(token, ">"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "<<") || !strcmp(token, ">>"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "+") || !strcmp(token, "-"))
+		return prec;
+	prec++;
+	if (!strcmp(token, "*") || !strcmp(token, "/") || !strcmp(token, "%"))
+		return prec;
+	prec++;
+	*ltr = 0;
+	if (!strcmp(token, "**"))
+		return prec;
+	exit(2);
+}
+
+
+
+static struct node *
+parse_expression_(int min_prec, const char **tokenp)
+{
+	struct node *left, *right;
+	const char *operator;
+	int prec, ltr;
+
+	left = parse_operand();
+	*tokenp = next_token();
+
+	while (*tokenp) {
+		prec = get_precedence(*tokenp, &ltr);
+		if (ltr ? prec <= min_prec : prec < min_prec)
+			break;
+		operator = *tokenp;
+		*tokenp = NULL;
+		right = parse_expression_(prec, tokenp);
+		left = operator_node(left, operator, right);
+		*tokenp = *tokenp ? *tokenp : next_token();
+	}
+
+	return left;
+}
+
+static struct node *
+parse_expression(void)
+{
+	return parse_expression_(-1, &(const char *){NULL});
+}
+
+
+int
+main(int argc, char *argv[])
+{
+	struct node *node;
+	tokens = &argv[1];
+	ntokens = (size_t)argc - 1u;
+
+	if (!(node = parse_expression()))
+		return 1;
+
+	print_node(node);
+	printf("\n");
+	return 0;
+}