Infix Calculator
Completed
Evaluate an infix expression of non-negative integers, + - * / and parentheses (no spaces) with two stacks, respecting precedence. Print the result (integer division).
Input
n, then n expressions.
Output
n results.
Example
Input
4 2+3*4 (2+3)*4 100/(2+3)-7 8-3-2
Output
14 20 13 3
Editor
C
Hints
Numbers go on the value stack; operators wait on the operator stack until something of lower or equal precedence arrives.
Solution explanation
This is Dijkstra's shunting-yard algorithm, evaluating as it goes.
Show solution
#include <stdio.h>
int values[100], vtop = 0;
char ops[100];
int otop = 0;
int prec(char op) {
return (op == '+' || op == '-') ? 1 : 2;
}
void apply() {
char op = ops[otop - 1];
otop--;
int b = values[vtop - 1];
int a = values[vtop - 2];
vtop -= 2;
int r;
if (op == '+') r = a + b;
else if (op == '-') r = a - b;
else if (op == '*') r = a * b;
else r = a / b;
values[vtop] = r;
vtop++;
}
int main() {
int n;
char e[200];
scanf("%d", &n);
for (int t = 0; t < n; t++) {
scanf("%s", e);
vtop = 0;
otop = 0;
int i = 0;
while (e[i] != '\0') {
char c = e[i];
if (c >= '0' && c <= '9') {
int v = 0;
while (e[i] >= '0' && e[i] <= '9') {
v = v * 10 + (e[i] - '0');
i++;
}
values[vtop] = v;
vtop++;
continue;
}
if (c == '(') {
ops[otop] = c;
otop++;
} else if (c == ')') {
while (ops[otop - 1] != '(') apply();
otop--;
} else {
while (otop > 0 && ops[otop - 1] != '(' && prec(ops[otop - 1]) >= prec(c)) apply();
ops[otop] = c;
otop++;
}
i++;
}
while (otop > 0) apply();
printf("%d\n", values[0]);
}
return 0;
}