Expression Evaluator

Lab C++ Advanced 30 points

Evaluate infix expressions with integers, + - * / and parentheses (tokens separated by spaces) using the shunting-yard algorithm with two stacks. Print each result (integer division), or division by zero.

Input

n, then n expressions.

Output

n results.

Example

Input

5
2 + 3 * 4
( 2 + 3 ) * 4
100 / ( 2 + 3 ) - 7
8 - 3 - 2
1 / ( 2 - 2 )

Output

14
20
13
3
division by zero

Sample input available Sample output available

Editor

C++

Hints

Apply waiting operators of greater or equal precedence before pushing a new one.

Report division by zero through a return value - no exceptions.

Solution explanation

Shunting-yard handles precedence and left-to-right evaluation with two stacks.

Show solution

#include <iostream>
#include <sstream>
#include <stack>
#include <string>
using namespace std;

int prec(const string &op) { return (op == "+" || op == "-") ? 1 : 2; }

bool applyOp(stack<long long> &vals, const string &op) {
    long long b = vals.top(); vals.pop();
    long long a = vals.top(); vals.pop();
    if (op == "/" && b == 0) return false;
    if (op == "+") vals.push(a + b);
    else if (op == "-") vals.push(a - b);
    else if (op == "*") vals.push(a * b);
    else vals.push(a / b);
    return true;
}

int main() {
    int n;
    cin >> n;
    string line;
    getline(cin, line);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        istringstream in(line);
        stack<long long> vals;
        stack<string> ops;
        string t;
        bool ok = true;
        while (ok && in >> t) {
            if (t == "(") {
                ops.push(t);
            } else if (t == ")") {
                while (ok && ops.top() != "(") { ok = applyOp(vals, ops.top()); ops.pop(); }
                ops.pop();
            } else if (t == "+" || t == "-" || t == "*" || t == "/") {
                while (ok && !ops.empty() && ops.top() != "(" && prec(ops.top()) >= prec(t)) {
                    ok = applyOp(vals, ops.top());
                    ops.pop();
                }
                ops.push(t);
            } else {
                vals.push(stoll(t));
            }
        }
        while (ok && !ops.empty()) { ok = applyOp(vals, ops.top()); ops.pop(); }
        if (ok) cout << vals.top() << "\n";
        else cout << "division by zero\n";
    }
    return 0;
}

Output

Answer