In this Leetcode Basic Calculator II problem solution, we have given a string s which represents an expression, evaluate this expression, and return its value.
- The integer division should truncate toward zero.
- You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Problem solution in Python.
def calculate(self, s): s = s.replace(" ", "") pn = [1 if c=="+" else -1 for c in s if c in "+-"] sList = [self.cal(c) for c in s.replace("-", "+").split("+")] return sList[0] + sum([sList[i+1]*pn[i] for i in xrange(len(pn))]) def cal(self, s): # calculate the values of substrings "WITHOUT +-" if "*" not in s and "/" not in s: return int(s) md = [1 if c=="*" else -1 for c in s if c in "*/"] sList = [int(i) for i in s.replace("/", "*").split("*")] res, i = sList[0], 0 while res != 0 and i < len(md): if md[i] == 1: res *= sList[i+1] else: res //= sList[i+1] i += 1 return res
Problem solution in Java.
class Solution { public int calculate(String s) { Stack<Integer> stack=new Stack<>(); int len=s.length(); int num=0; int sign=1; char dm=' '; for(int i=0;i<len;i++){ char c=s.charAt(i); if(Character.isDigit(c)){ int temp=0; while(i<len && Character.isDigit(s.charAt(i))){ temp=temp*10+s.charAt(i)-'0'; i++; } i--; if(dm=='*')num=num*temp; else if(dm=='/')num=num/temp; else num=temp; dm=' '; } else if(c=='*') dm='*'; else if(c=='/')dm='/'; else if(c=='+'){stack.push(sign*num);sign=1;} else if(c=='-'){stack.push(sign*num);sign=-1;} } num*=sign; while(!stack.isEmpty()){ num+=stack.pop(); } return num; } }
Problem solution in C++.
class Solution { public: int calculate(string s) { char sign = '+'; int val = 0; int ans; vector<int> stack; for (int i=0; i<s.size(); i++) { auto c = s[i]; if (isdigit(c)) { val = 10 * val + (c-'0'); } if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.size()-1) { if (sign == '+') { stack.push_back(val); } if (sign == '-') { stack.push_back(-1 * val); } if (sign == '*') { auto last = stack.back(); stack.pop_back(); stack.push_back(last * val); } if (sign == '/') { auto last = stack.back(); stack.pop_back(); stack.push_back(last / val); } sign = c; val = 0; } } int sum = 0; for (auto num: stack) sum += num; return sum; } };
Problem solution in C.
static bool ft_expect_token(char **p, int const c) { while (0 != isspace(**p)) ++(*p); if (**p != c) return (false); ++(*p); return (true); } static int ft_parse_digit(char **p) { return (*(*p)++ - '0'); } static int ft_parse_number(char **p) { int total; while (0 != isspace(**p)) ++(*p); total = 0; while (0 != isdigit(**p)) total = total * 10 + ft_parse_digit(p); return (total); } static int ft_parse_factor(char **p) { return (ft_parse_number(p)); } static int ft_parse_term(char **p) { int result; result = ft_parse_factor(p); while (true) { if (true == ft_expect_token(p, '*')) result *= ft_parse_factor(p); else if (true == ft_expect_token(p, '/')) result /= ft_parse_factor(p); else break ; } return (result); } static int ft_parse_expression(char **p) { int result; if (true == ft_expect_token(p, '-')) result = -ft_parse_term(p); else result = ft_parse_term(p); while (true) { if (true == ft_expect_token(p, '+')) result += ft_parse_term(p); else if (true == ft_expect_token(p, '-')) result -= ft_parse_term(p); else break ; } return (result); } int calculate(char *s) { return (ft_parse_expression(&s)); }
0 Comments