/* 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;
}