shuntyard.c (raw) (1781B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <stdbool.h> 5 #include "stack.h" 6 7 char isop(char c); 8 int op_isleft(char c); // associativity (left/right) 9 int op_prec(char c); // precendence 10 11 int main(int argc, char *argv[]) 12 { 13 size_t len = 0; 14 for (int i = 1; i < argc; ++i) { 15 if (argv[i]) 16 len += strlen(argv[i]); 17 } 18 char *input = calloc(1, len+1); 19 for (int i = 1; i < argc; ++i) { 20 strcat(input, argv[i]); 21 } 22 puts(input); 23 24 struct stack *ops = stack_new(); 25 struct stack *out = stack_new(); 26 27 int tok; 28 for (size_t i = 0; i < len+1; ++i) { 29 tok = input[i]; 30 if (isop(tok)) { 31 while (!stack_isempty(ops)) { 32 int assoc = op_isleft(tok); 33 int prec = op_prec(tok); 34 if ((assoc && prec <= op_prec(stack_peek(ops))) || 35 (!assoc && prec < op_prec(stack_peek(ops)))) { 36 stack_push(out, stack_pop(ops)); 37 } else { 38 break; 39 } 40 } 41 stack_push(ops, tok); 42 } else if (tok == '(') { 43 stack_push(ops, tok); 44 } else if (tok == ')') { 45 while (stack_peek(ops) != '(') 46 stack_push(out, stack_pop(ops)); 47 stack_pop(ops); 48 } else { 49 stack_push(out, tok); 50 } 51 } 52 53 while (!stack_isempty(ops)) 54 stack_push(out, stack_pop(ops)); 55 56 for (int i = 0; i <= out->sp; ++i) 57 putchar(out->s[i]); 58 puts(""); 59 60 return 0; 61 } 62 63 char isop(char c) 64 { 65 char ret = 0; 66 switch (c) { 67 case '*': 68 case '/': 69 case '-': 70 case '+': 71 case '^': 72 ret = c; 73 break; 74 } 75 return ret; 76 } 77 78 int op_isleft(char op) 79 { 80 int ret = 0; 81 switch (op) { 82 case '*': 83 case '/': 84 case '+': 85 case '-': 86 ret = 1; 87 break; 88 case '^': 89 break; 90 } 91 return ret; 92 } 93 94 int op_prec(char op) 95 { 96 int ret = 0; 97 switch (op) { 98 case '^': 99 ret = 4; 100 break; 101 case '*': 102 case '/': 103 ret = 3; 104 break; 105 case '+': 106 case '-': 107 ret = 2; 108 break; 109 } 110 return ret; 111 }