shuntyard

commit 2b81f891f712c5b3e486dab4d4ee8993ad2ecbea
Author: gearsix <gearsix@tuta.io>
Date:   Mon, 15 Nov 2021 18:24:00 +0000

git init

Diffstat:
A
shuntyard.c
 | 
111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
stack.c
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
A
stack.h
 | 
23
+++++++++++++++++++++++

3 files changed, 177 insertions(+), 0 deletions(-)
diff --git a/shuntyard.c b/shuntyard.c
@@ -0,0 +1,111 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+#include "stack.h"
+
+char isop(char c);
+int  op_isleft(char c); // associativity (left/right)
+int  op_prec(char c);   // precendence
+
+int main(int argc, char *argv[])
+{
+	size_t len = 0;
+	for (int i = 1; i < argc; ++i) {
+		if (argv[i])
+		len += strlen(argv[i]);
+	}
+	char *input = calloc(1, len+1);
+	for (int i = 1; i < argc; ++i) {
+		strcat(input, argv[i]);
+	}
+	puts(input);
+
+	struct stack *ops = stack_new();
+	struct stack *out = stack_new();
+
+	int tok;
+	for (size_t i = 0; i < len+1; ++i) {
+		tok = input[i];
+		if (isop(tok)) {
+			while (!stack_isempty(ops)) {
+				int assoc = op_isleft(tok);
+				int prec = op_prec(tok);
+				if ((assoc && prec <= op_prec(stack_peek(ops))) ||
+					(!assoc && prec < op_prec(stack_peek(ops)))) {
+					stack_push(out, stack_pop(ops));
+				} else {
+					break;
+				}
+			}
+			stack_push(ops, tok);
+		} else if (tok == '(') {
+			stack_push(ops, tok);
+		} else if (tok == ')') {
+			while (stack_peek(ops) != '(')
+				stack_push(out, stack_pop(ops));
+			stack_pop(ops);
+		} else {
+			stack_push(out, tok);
+		}
+	}
+
+	while (!stack_isempty(ops))
+		stack_push(out, stack_pop(ops));
+
+	for (int i = 0; i <= out->sp; ++i)
+		putchar(out->s[i]);
+	puts("");
+
+	return 0;
+}
+
+char isop(char c)
+{
+	char ret = 0;
+	switch (c) {
+		case '*':
+		case '/':
+		case '-':
+		case '+':
+		case '^':
+			ret = c;
+			break;
+	}
+	return ret;
+}
+
+int op_isleft(char op)
+{
+	int ret = 0;
+	switch (op) {
+		case '*':
+		case '/':
+		case '+':
+		case '-':
+			ret = 1;
+			break;
+		case '^':
+			break;
+	}
+	return ret;
+}
+
+int op_prec(char op)
+{
+	int ret = 0;
+	switch (op) {
+		case '^':
+			ret = 4;
+			break;
+		case '*':
+		case '/':
+			ret = 3;
+			break;
+		case '+':
+		case '-':
+			ret = 2;
+			break;
+	}
+	return ret;
+}
diff --git a/stack.c b/stack.c
@@ -0,0 +1,43 @@
+#include "stack.h"
+
+struct stack *stack_new()
+{
+	const size_t siz = 1024;
+
+	struct stack *s = malloc(sizeof(struct stack *));
+	s->s = malloc(siz);
+	s->sp = -1;
+	s->siz = siz;
+
+	return s;
+}
+
+int stack_isempty(struct stack *s)
+{
+	return (s->sp == -1);
+}
+
+int stack_isfull(struct stack *s)
+{
+	return (s->sp == s->siz);
+}
+
+int stack_peek(struct stack *s)
+{
+	if (!stack_isempty(s))
+		return s->s[s->sp];
+	return 0;
+}
+
+void stack_push(struct stack *s, int item)
+{
+	if (!stack_isfull(s))
+		s->s[++s->sp] = item;
+}
+
+int stack_pop(struct stack *s)
+{
+	if (!stack_isempty(s))
+		return s->s[s->sp--];
+	return 0;
+}
diff --git a/stack.h b/stack.h
@@ -0,0 +1,23 @@
+#ifndef STACK_H
+#define STACK_H
+
+#include <stdlib.h>
+
+struct stack {
+	char *s;
+	int sp, siz;
+};
+
+struct stack *stack_new();
+
+int  stack_isempty(struct stack *s);
+
+int  stack_isfull(struct stack *s);
+
+int  stack_peek(struct stack *s);
+
+void stack_push(struct stack *s, int item);
+
+int  stack_pop(struct stack *s);
+
+#endif