fork download
copy 
  1. #include <stdbool.h>
  2. #include <stddef.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6.  
  7. //#define TESTING
  8.  
  9. #ifdef TESTING
  10. 	#define TEST_ASSERT(maCond) do { if (!(maCond)) { printf("%d: %s\n", __LINE__, #maCond); exit(1); } } while (0)
  11. 	#define TEST_ASSERT_MSG(maCond, maFormat, maMsg) \
  12. 		do { \
  13. 			if (!(maCond)) { printf("%d: %s: '" maFormat "'\n", __LINE__, #maCond, (maMsg)); exit(1); } \
  14. 		} while (0)
  15. 	#define IF_TESTING(...) __VA_ARGS__
  16. #else
  17. 	#define TEST_ASSERT(maCond) do {} while (0)
  18. 	#define TEST_ASSERT_MSG(maCond, maFormat, maMsg) do {} while(0)
  19. 	#define IF_TESTING(...)
  20. #endif
  21.  
  22.  
  23. //#define TRACING
  24.  
  25. #ifdef TRACING
  26. 	#define TRACE(msg, ...) printf(msg "\n", __VA_ARGS__)
  27. #else
  28. 	#define TRACE(...) do {} while (0)
  29. #endif
  30.  
  31.  
  32. #define MAX_NODE_COUNT (255)
  33. #define MAX_INPUT_SIZE (255)
  34.  
  35.  
  36. enum ParsingContext
  37. {
  38. 	CONTEXT_FIRST_TERM
  39. 	, CONTEXT_ADDITIVE_EXPRESSION
  40. 	, CONTEXT_NONFIRST_TERM
  41. };
  42.  
  43.  
  44. struct ExprNode
  45. {
  46. 	char type;
  47. 	struct ExprNode *child[2];
  48. };
  49.  
  50.  
  51. struct NodeMemory
  52. {
  53. 	struct ExprNode data[MAX_NODE_COUNT];
  54. 	struct ExprNode *end;
  55. };
  56.  
  57.  
  58. struct ExprNode* createNode(struct NodeMemory *mem, char type)
  59. {
  60. 	struct ExprNode *node = mem->end++;
  61. 	TEST_ASSERT(mem->end - mem->data <= MAX_NODE_COUNT);
  62. 	node->type = type;
  63. 	IF_TESTING(
  64. 		node->child[0] = node->child[1] = NULL;
  65. 	)
  66. 	return node;
  67. }
  68.  
  69.  
  70. struct ExprNode* moveToChild(
  71. 	struct NodeMemory * restrict mem
  72. 	, struct ExprNode * restrict node
  73. 	, size_t idxChild
  74. 	, char newParentType
  75. )
  76. {
  77. 	struct ExprNode * result = createNode(mem, newParentType);
  78. 	result->child[idxChild] = node;
  79. 	return result;
  80. }
  81.  
  82.  
  83. char readChar(const char * restrict * restrict in)
  84. {
  85. 	char c = **in;
  86. 	++*in;
  87. 	return c;
  88. }
  89.  
  90.  
  91. void writeChar(char * restrict * restrict out, char c)
  92. {
  93. 	**out = c;
  94. 	++*out;
  95. }
  96.  
  97.  
  98. struct ExprNode* parse(
  99. 	struct NodeMemory * restrict mem
  100. 	, const char * restrict * restrict in
  101. 	, struct ExprNode * restrict root
  102. 	, enum ParsingContext context
  103. )
  104. {
  105. 	TEST_ASSERT(root != NULL);
  106. 	bool skipStart = (context == CONTEXT_NONFIRST_TERM);
  107. 	// Left operand
  108. 	if (!skipStart) {
  109. 		switch (**in) {
  110. 			case '(':
  111. 				++*in;
  112. 				root = parse(mem, in, root, CONTEXT_FIRST_TERM);
  113. 				TEST_ASSERT_MSG(**in == ')', "%c", **in);
  114. 				++*in;
  115. 				break;
  116. 			default:
  117. 				TEST_ASSERT_MSG(
  118. 					**in != ')'
  119. 					&& **in != '+'
  120. 					&& **in != '-'
  121. 					&& **in != '*'
  122. 					&& **in != '/'
  123. 					&& **in != '\n'
  124. 					, "%c", **in
  125. 				);
  126. 				root->type = readChar(in);
  127. 				break;
  128. 		}
  129. 	}
  130. 	for (;;) {
  131. 		// Operator
  132. 		if (!skipStart) {
  133. 			switch (**in) {
  134. 				case '\n':
  135. 				case ')':
  136. 					TEST_ASSERT(root != NULL);
  137. 					TEST_ASSERT(root->type != '.');
  138. 					return root;
  139. 				case '+':
  140. 				case '-':
  141. 					if (context == CONTEXT_NONFIRST_TERM) {
  142. 						TEST_ASSERT(root != NULL);
  143. 						TEST_ASSERT(root->type != '.');
  144. 						return root;
  145. 					}
  146. 					TEST_ASSERT(
  147. 						(context == CONTEXT_ADDITIVE_EXPRESSION)
  148. 						==
  149. 						(root->type == '+' || root->type == '-')
  150. 					);
  151. 					context = CONTEXT_ADDITIVE_EXPRESSION;
  152. 					root = moveToChild(mem, root, 0, readChar(in));
  153. 					break;
  154. 				case '*':
  155. 				case '/':
  156. 					if (context == CONTEXT_ADDITIVE_EXPRESSION) {
  157. 						TEST_ASSERT(root->child[1]->type != '.');
  158. 						root->child[1] = moveToChild(mem, root->child[1], 0, readChar(in));
  159. 						root->child[1] = parse(mem, in, root->child[1], CONTEXT_NONFIRST_TERM);
  160. 						continue;	// Parsed up to next operator or teminator
  161. 					}
  162. 					root = moveToChild(mem, root, 0, readChar(in));
  163. 					break;
  164. 				default:
  165. 					TEST_ASSERT(false);
  166. 					break;
  167. 			}
  168. 		}
  169. 		skipStart = false;
  170. 		// Right operand
  171. 		switch (**in) {
  172. 			case '(':
  173. 				++*in;
  174. 				root->child[1] = parse(mem, in, createNode(mem, '.'), CONTEXT_FIRST_TERM);
  175. 				TEST_ASSERT_MSG(**in == ')', "%c", **in);
  176. 				++*in;
  177. 				break;
  178. 			default:
  179. 				TEST_ASSERT_MSG(
  180. 					**in != ')'
  181. 					&& **in != '+'
  182. 					&& **in != '-'
  183. 					&& **in != '*'
  184. 					&& **in != '/'
  185. 					&& **in != '\n'
  186. 					, "%c", **in
  187. 				);
  188. 				root->child[1] = createNode(mem, readChar(in));
  189. 				break;
  190. 		}
  191. 	}
  192. }
  193.  
  194.  
  195.  
  196. void serialiseTree(const struct ExprNode * restrict node, char * restrict * restrict out, char parentType, bool isLeftChild)
  197. {
  198. 	IF_TESTING(
  199. 		if (!node) {
  200. 			writeChar(out, 'N');
  201. 			return;
  202. 		}
  203. 	)
  204. 	TEST_ASSERT(
  205. 		parentType == '+'
  206. 		|| parentType == '-'
  207. 		|| parentType == '*'
  208. 		|| parentType == '/'
  209. 	);
  210. 	bool paren = false;
  211. 	switch (node->type) {
  212. 		case '+':
  213. 		case '-':
  214. 			paren = (
  215. 				parentType == '*'
  216. 				|| parentType == '/'
  217. 				|| (parentType == '-' && !isLeftChild)
  218. 			);
  219. 			break;
  220. 		case '*':
  221. 		case '/':
  222. 			paren = (parentType == '/' && !isLeftChild);
  223. 			break;
  224. 		default:
  225. 			writeChar(out, node->type);
  226. 			return;
  227. 	}
  228. 	if (paren) {
  229. 		writeChar(out, '(');
  230. 	}
  231. 	serialiseTree(node->child[0], out, node->type, true);
  232. 	writeChar(out, node->type);
  233. 	serialiseTree(node->child[1], out, node->type, false);
  234. 	if (paren) {
  235. 		writeChar(out, ')');
  236. 	}
  237. }
  238.  
  239.  
  240.  
  241. void createTree(struct NodeMemory *mem)
  242. {
  243. 	char expr[MAX_INPUT_SIZE + 2];
  244. 	fgets(expr, sizeof(expr), stdin);
  245. 	const char *in = expr;
  246. 	if (*in == '\n') {
  247. 		fputs(expr, stdout);
  248. 		return;
  249. 	}
  250. 	struct ExprNode *root = parse(mem, &in, createNode(mem, '.'), CONTEXT_FIRST_TERM);
  251. 	TEST_ASSERT(*in == '\n');
  252. 	TEST_ASSERT(root != NULL);
  253. 	char *out = expr;
  254. 	serialiseTree(root, &out, '+', true);
  255. 	*out++ = '\n';
  256. 	*out = 0;
  257. 	TEST_ASSERT(out - expr < sizeof(expr));
  258. 	fputs(expr, stdout);
  259. }
  260.  
  261.  
  262.  
  263. void runCase(void)
  264. {
  265. 	struct NodeMemory mem;
  266. 	mem.end = mem.data;
  267. 	createTree(&mem);
  268. }
  269.  
  270.  
  271.  
  272. int main(void) {
  273. 	int caseCount;
  274. 	fscanf(stdin, "%d\n", &caseCount);
  275. 	for (int idxCase = 0; idxCase < caseCount; ++idxCase) {
  276. 		runCase();
  277. 	}
  278. 	return 0;
  279. }
  280.  
Success #stdin #stdout 0s 2252KB
comments (?)
stdin
copy 
2
a+b*c
a+(a-a)+((a-a))+b*(c+d-e+(e-f)+a*a/a/(a/a))
stdout
copy 
a+b*c
a+a-a+a-a+b*(c+d-e+e-f+a*a/a/(a/a))
https://ideone.com/grzWm1
CMEXPR
language:
C99 (gcc 8.3)
created:
10 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!