Skip to content

Instantly share code, notes, and snippets.

@dylanliuh2o
Created June 15, 2023 14:37
Show Gist options
  • Save dylanliuh2o/81b3603289c645889219f1836d5c5bd3 to your computer and use it in GitHub Desktop.
Save dylanliuh2o/81b3603289c645889219f1836d5c5bd3 to your computer and use it in GitHub Desktop.
evaluate expression contains @ and $
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment