LeetCode Hard Problem: Basic Calculator III
Problem is here: https://leetcode.com/problems/basic-calculator-iii/description/
Now given the number of submissions and acceptances, this is definitely not a super trivial problem:
Now since I had some ExpressionEvaluation code hanging around, I reused the code with some few modifications:
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open
( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces
The expression string contains only non-negative integers,
+, -, *, / operators , open ( and closing parentheses ) and empty spaces
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 6-4 / 2 " = 4 "2*(5+5*2)/3+(6/2+8)" = 21 "(2+6* 3+5- (3*14/7+2)*5)+3"=-12
Now given the number of submissions and acceptances, this is definitely not a super trivial problem:
Now since I had some ExpressionEvaluation code hanging around, I reused the code with some few modifications:
- Keep it to basic operations only
- Remove spaces from the expression
- Change the data type during the evaluation to BigInteger. That way you avoid over/underflow partial calculations. In the very end, cast the result back to Integer
And that's it! Code is down below, cheers, Marcelo
public class Solution
{
public int Calculate(string s)
{
BigInteger retVal = 0;
ExpressionEvaluation(RemoveSpaces(s), out retVal);
return (int)retVal;
}
private string RemoveSpaces(string s)
{
if (String.IsNullOrEmpty(s)) return s;
string retVal = "";
for (int i = 0; i < s.Length; i++)
if (s[i] != ' ') retVal += s[i].ToString();
return retVal;
}
private bool ExpressionEvaluation(string expression,
out BigInteger result)
{
result = 0;
if (expression == null)
{
return false;
}
if (expression.Trim().Length == 0)
{
return true;
}
if (BigInteger.TryParse(expression, out result))
{
return true;
}
if (expression.Length > 2 &&
expression.StartsWith("(") &&
expression.EndsWith(")") &&
IsWellFormedBrackets(expression.Substring(1, expression.Length - 2)))
{
return ExpressionEvaluation(expression.Substring(1, expression.Length - 2), out result);
}
char[] operators = new char[] { '+', '-', '*', '/' };
foreach (char op in operators)
{
int bracketsCount = 0;
for (int i = expression.Length - 1; i >= 0; i--)
{
if (expression[i] == '(')
{
bracketsCount++;
}
else if (expression[i] == ')')
{
bracketsCount--;
}
if (expression[i] == op &&
bracketsCount == 0)
{
BigInteger value1 = 0;
BigInteger value2 = 0;
string part1 = "";
string part2 = "";
if (i > 0)
{
part1 = expression.Substring(0, i);
}
if (i + 1 < expression.Length)
{
part2 = expression.Substring(i + 1);
}
if (!ExpressionEvaluation(part1, out value1))
{
return false;
}
if (!ExpressionEvaluation(part2, out value2))
{
return false;
}
switch (op)
{
case '+':
result = value1 + value2;
break;
case '-':
result = value1 - value2;
break;
case '*':
result = value1 * value2;
break;
case '/':
if (value2 == 0)
{
return false;
}
result = value1 / value2;
break;
}
return true;
}
}
}
return false;
}
private static bool IsWellFormedBrackets(string expression)
{
if (expression == null ||
expression.Trim().Length == 0)
{
return true;
}
int bracketsCount = 0;
for (int i = 0; i < expression.Length; i++)
{
if (expression[i] == '(')
{
bracketsCount++;
}
else if (expression[i] == ')')
{
bracketsCount--;
}
if (bracketsCount < 0)
{
return false;
}
}
return bracketsCount == 0;
}
}
very nice, Marcelo! I decided to use a different way of solving this problem by reducing it to a much simpler problem of evaluating an expression defined in postfix form. In order to do this, we just need to convert an infix form to a postfix form and fortunately Dijkstra, as always, invented an awesome algorithm to do just that and it's called shunting yard algorithm. What I like about this solution is that the problem is nicely split into 2 much simpler ones and it also works very well for evaluating expressions with variables, since we don't have to re-parse the entire expression every time in order to evaluate it. As always, my convoluted solution below:
ReplyDeleteclass Solution {
private:
int operator_precedence(char op) {
if (op == '(') return 1;
if (op == '+' || op == '-') return 2;
return 3; // * or /
}
vector parse(const string& text) {
stack operators;
vector tokens;
int i = 0;
while (i < text.size()) {
if (text[i] == ' ') {
i += 1;
} else if (text[i] == '(') {
operators.push(text[i++]);
} else if (text[i] == ')') {
while (operators.top() != '(') {
tokens.emplace_back(1, operators.top());
operators.pop();
}
operators.pop();
i += 1;
} else if (isdigit(text[i])) {
int start = i++;
while (i < text.size() && isdigit(text[i])) { i += 1; }
tokens.emplace_back(text.substr(start, i - start));
} else {
while (!operators.empty() && operator_precedence(operators.top()) >= operator_precedence(text[i])) {
tokens.emplace_back(1, operators.top());
operators.pop();
}
operators.push(text[i++]);
}
}
while (!operators.empty()) {
tokens.emplace_back(1, operators.top());
operators.pop();
}
return tokens;
}
function to_function(char op) {
switch (op) {
case '+': return plus();
case '-': return minus();
case '/': return divides();
case '*': return multiplies();
}
}
long evaluate(const vector& tokens) {
stack operands;
for (const string& token: tokens) {
if (isdigit(token.front())) {
operands.push(stol(token));
} else {
auto func = to_function(token.front());
long operand_2 = operands.top(); operands.pop();
long operand_1 = operands.top(); operands.pop();
operands.push(func(operand_1, operand_2));
}
}
return operands.top();
}
public:
int calculate(const string& text) {
if (text.empty()) return 0;
const auto& tokens = parse(text);
return evaluate(tokens);
}
};
Cheers,
Taras
what (const string& text) even mean?
DeleteCan't you just convert it to leetcode format? Thanks!
public int Calculate(string s)
{
BigInteger retVal = 0;
ExpressionEvaluation(RemoveSpaces(s), out retVal);
return (int)retVal;
}
(const string& text) means that it's a C++ and it's in leetcode format ;)
Delete