evaluate expression contains @ and $

evalexpr.cc

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <string>

#define DEBUG 1

enum class Operator {
    AT = 0,
    DOLLAR
};

int evalOperator(Operator op, int x, int y)
{
    if (op == Operator::AT) {
        return 2 * x + y + 3;
    }

    if (op == Operator::DOLLAR) {
        return 3 * x + 2 * y + 1;
    }

    return 0;
}

std::vector<std::string> convertStringToInfixExpr(const std::string &str)
{
    std::vector<std::string> infix_expr;
    std::string::size_type start_pos = 0;

    for (int i = 0; i < (int)str.length(); i++) {
        char ch = str[i];
        if (ch == '@' || ch == '$') {
            infix_expr.push_back(str.substr(start_pos, i-start_pos));
            infix_expr.push_back(std::string(1, ch));
            start_pos = i + 1;
        } else if (i == (int)str.length()-1) {
            infix_expr.push_back(str.substr(start_pos, i-start_pos+1));
        }
    }

#if DEBUG
    std::cout << "infix_expr: ";
    for (auto token : infix_expr) {
        std::cout << token << " ";
    }
    std::cout << std::endl;
#endif

    return infix_expr;
}

std::map<std::string, int> operator_priority {
    { "$", 0 },
    { "@", 1 }
};

std::vector<std::string> convertInfixExprToSuffixExpr(std::vector<std::string> infix_expr)
{
    std::vector<std::string> suffix_expr;
    std::stack<std::string> operator_stack;

    for (auto token : infix_expr) {
        if (token != "@" && token != "$") {
            suffix_expr.push_back(token);
        } else {
            while (!operator_stack.empty() && operator_priority[operator_stack.top()] >= operator_priority[token]) {
                suffix_expr.push_back(operator_stack.top());
                operator_stack.pop();
            }
            operator_stack.push(token);
        }
    }
    while (!operator_stack.empty()) {
        suffix_expr.push_back(operator_stack.top());
        operator_stack.pop();
    }

#if DEBUG
    std::cout << "suffix_expr: ";
    for (auto token : suffix_expr) {
        std::cout << token << " ";
    }
    std::cout << std::endl;
#endif

    return suffix_expr;
}

int evalSuffixExpr(std::vector<std::string> suffix_expr)
{
    std::stack<int> operand_stack;

    for (auto token : suffix_expr) {
        if (token == "@") {
            int y = operand_stack.top(); operand_stack.pop();
            int x = operand_stack.top(); operand_stack.pop();
            int ans = evalOperator(Operator::AT, x, y);
            operand_stack.push(ans);
        } else if (token == "$") {
            int y = operand_stack.top(); operand_stack.pop();
            int x = operand_stack.top(); operand_stack.pop();
            int ans = evalOperator(Operator::DOLLAR, x, y);
            operand_stack.push(ans);
        } else {
            int operand = std::stoi(token);
            operand_stack.push(operand);
        }
    }

    return operand_stack.top();
}

int main()
{
    std::vector<std::string> testcases {
        "11@2$3@14"
    };

    for (auto testcase : testcases) {
        std::vector<std::string> infix_expr = convertStringToInfixExpr(testcase);
        std::vector<std::string> suffix_expr = convertInfixExprToSuffixExpr(infix_expr);

        int result = evalSuffixExpr(suffix_expr);

        std::cout << "testcase: " << testcase << std::endl;
        std::cout << "result: " << result << std::endl;
    }

    return 0;
}