In this Leetcode Basic Calculator problem solution, we have given a string s representing a valid expression, implement a basic calculator to evaluate it and return the result of the evaluation.
Problem solution in Python.
class Solution: def calculate(self, s: str) -> int: res, num, stack, sign = 0, 0, [], '+' for i in range(len(s)): if '0'<=s[i]<='9': num = num*10 + ord(s[i]) - ord('0') if s[i] in '+-)' or i == len(s)-1: if sign == '+': res += num else: res += -num num = 0 sign = s[i] if s[i] == '(': stack.append(res) stack.append(sign) sign = '+' res = 0 elif s[i] == ')': sign = stack.pop() res1 = stack.pop() res = res+res1 if sign == '+' else res1-res num = 0 sign = '+' # print(s[i],'---',num,'---',res, stack) return res
Problem solution in Java.
public int calculate(String s) { return helper(0, s, new int[1]); } private int helper(int start, String s, int[] nextPos){ int pt = start, cur = 0, val = 0; int sign = 1; while(pt < s.length()){ if(s.charAt(pt) == ' ') pt++; else if(s.charAt(pt) >= '0' && s.charAt(pt) <= '9') cur = cur * 10 + (s.charAt(pt++) - '0'); else{ val += sign * cur; cur = 0; if(s.charAt(pt) == '+'){ sign = 1; pt++; }else if(s.charAt(pt) == '-'){ sign = -1; pt++; }else if(s.charAt(pt) == '('){ val += sign * helper(pt+1, s, nextPos); pt = nextPos[0]; }else if(s.charAt(pt) == ')'){ nextPos[0] = pt+1; return val; } } } val += sign * cur; return val; }
Problem solution in C++.
class Solution { public: int calculate(string s) { stack<int> operand; stack<pair<int, bool>> stackSize; bool sign = true; int retVal = 0; int startIdx = 0; for (int i = 0; i <= s.length(); ++i) { if (i == s.length() || s[i] == ')') { int remainingSize = 0; bool localSign = true; if (!stackSize.empty()) { remainingSize = stackSize.top().first; localSign = stackSize.top().second; } int temp = 0; while (operand.size() != remainingSize) { temp += operand.top(); operand.pop(); } if (localSign == false) { temp *= -1; } if (i != s.length()) operand.push(temp); else retVal = temp; stackSize.pop(); } else if (s[i] == '(') { stackSize.push({operand.size(), sign}); sign = true; } else if (s[i] >= '0' && s[i] <= '9') { if (i > 0 && !(s[i - 1] >= '0' && s[i - 1] <= '9')) { startIdx = i; } if (i == s.length() - 1 || !(s[i + 1] >= '0' && s[i + 1] <= '9')) { int num = stoi(s.substr(startIdx, i - startIdx + 1)); if (!sign) num *= -1; operand.push(num); } } else if (s[i] == '+') { sign = true; } else if (s[i] == '-') { sign = false; } } return retVal; } };
Problem solution in C.
char*s;calculate(char*x){s=x;return e();} void b(){while(*s==' ')s++;} c(char*t){b();return strchr(t,*s)?*s++:0;} i(){b();char*p=s;while(isdigit(*s)){s++;}char h=*s;*s=0;int r=atoi(p);*s=h;return r;} p(){int r;if(c("(")){r=e();c(")");}else r=i();return r;} u(){return c("-")?-p():p();} e(){int o,r=u();while(o=c("+-")){if(o=='+')r+=u();else r-=u();}return r;}
0 Comments