Created
June 15, 2023 14:37
-
-
Save dylanliuh2o/81b3603289c645889219f1836d5c5bd3 to your computer and use it in GitHub Desktop.
evaluate expression contains @ and $
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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