Created
January 20, 2026 10:37
-
-
Save lakshyaraj2006/b48413a84fa3d13d073a7c451201073a to your computer and use it in GitHub Desktop.
This solution solves LeetCode Problems 224, 227 & 772
This file contains hidden or 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
| class Solution { | |
| public: | |
| bool isOperator(char c) { | |
| return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'; | |
| } | |
| int precedence(char op) { | |
| if (op == '+' || op == '-') return 1; | |
| if (op == '*' || op == '/') return 2; | |
| if (op == '^') return 3; | |
| return 0; | |
| } | |
| bool isRightAssociative(char op) { | |
| return op == '^'; | |
| } | |
| long long applyOp(long long a, long long b, char op) { | |
| if (op == '+') return a + b; | |
| if (op == '-') return a - b; | |
| if (op == '*') return a * b; | |
| if (op == '/') return a / b; | |
| if (op == '^') { | |
| long long res = 1; | |
| while (b--) res *= a; | |
| return res; | |
| } | |
| return 0; | |
| } | |
| int calculate(string s) { | |
| stack<long long> values; | |
| stack<char> ops; | |
| int n = s.size(); | |
| for (int i = 0; i < n; i++) { | |
| char c = s[i]; | |
| if (c == ' ') continue; | |
| if (isdigit(c)) { | |
| long long num = 0; | |
| while (i < n && isdigit(s[i])) { | |
| num = num * 10 + (s[i] - '0'); | |
| i++; | |
| } | |
| i--; | |
| values.push(num); | |
| } | |
| else if (c == '(') { | |
| ops.push(c); | |
| } | |
| else if (c == ')') { | |
| while (!ops.empty() && ops.top() != '(') { | |
| long long b = values.top(); values.pop(); | |
| long long a = values.top(); values.pop(); | |
| char op = ops.top(); ops.pop(); | |
| values.push(applyOp(a, b, op)); | |
| } | |
| ops.pop(); | |
| } | |
| else { | |
| char op = c; | |
| if (op == '-') { | |
| int j = i - 1; | |
| while (j >= 0 && s[j] == ' ') j--; | |
| if (j < 0 || s[j] == '(' || isOperator(s[j])) { | |
| values.push(0); | |
| } | |
| } | |
| if (c == '*' && i + 1 < n && s[i + 1] == '*') { | |
| op = '^'; | |
| i++; | |
| } | |
| while (!ops.empty() && | |
| ops.top() != '(' && | |
| (precedence(ops.top()) > precedence(op) || | |
| (precedence(ops.top()) == precedence(op) && !isRightAssociative(op)))) { | |
| long long b = values.top(); values.pop(); | |
| long long a = values.top(); values.pop(); | |
| char topOp = ops.top(); ops.pop(); | |
| values.push(applyOp(a, b, topOp)); | |
| } | |
| ops.push(op); | |
| } | |
| } | |
| while (!ops.empty()) { | |
| long long b = values.top(); values.pop(); | |
| long long a = values.top(); values.pop(); | |
| char op = ops.top(); ops.pop(); | |
| values.push(applyOp(a, b, op)); | |
| } | |
| return (int)values.top(); | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment