Evaluate a given expression
Given an expression containing numeric operands with addition and subtraction operators, evaluate it. Assume that the expression is valid and may contain sub-expressions enclosed in opening and closing braces.
For example,
Output: -16
Input: s = -10+(5+(12+8)-2)+1
Output: 14
We can easily compute a mathematical expression containing only addition and subtraction operators using a stack. The idea is based on the fact that whenever a negative sign is present outside of parentheses, all numbers inside the parentheses have their sign reversed.
We traverse the given expression from left to right. If the current character of the expression is a digit, construct the full number; otherwise, if the current character is a plus or minus sign, add the preceding number to the result in accordance with the sign outside the parentheses (if any). Here, '+' would have no impact on the sign inside the parentheses, whereas '-' would negate the sign inside the parentheses. We push the sign to the stack if the current character is an opening brace, and pop the sign from the stack if the current character is a closing brace.
This approach is demonstrated below in C++, Java, and Python. Note that the sign before each set of parenthesis is stored in a stack.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <iostream> #include <stack> #include <cctype> using namespace std; int eval(string exp) { int result = 0; // stores the last number int n = 0; // sign is 1 for positive and -1 for negative int sign = 1; // take a stack to store the sign stack<int> stack; stack.push(sign); // do for each character for (char c: exp) { // if the current character is a digit, construct the full number if (isdigit(c)) { n = n * 10 + (c - '0'); } // if the current character is a plus operator else if (c == '+') { // include the number before it in the result result += sign * n; // reset the number n = 0; // '+' would not affect the sign within the parentheses sign = stack.top(); } // if the current character is a minus operator else if (c == '-') { // include the number before it in the result result += sign * n; // reset the number n = 0; // '-' would negate the sign within the parentheses sign = stack.top() * -1; } // if the current character is an opening brace, push the sign to the stack else if (c == '(') { stack.push(sign); } // if the current character is a closing brace, pop the sign from the stack else if (c == ')') { stack.pop(); } } // add the last number and return the result result += sign * n; return result; } int main() { string exp = "-10+(5+(12+8)-2)+1"; cout << eval(exp) << endl; return 0; } |
Output:
14
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
import java.util.Stack; class Main { public static int eval(String exp) { int result = 0; // stores the last number int n = 0; // sign is 1 for positive and -1 for negative int sign = 1; // take a stack to store the sign Stack<Integer> stack = new Stack<>(); stack.push(sign); // do for each character for (char c: exp.toCharArray()) { // if the current character is a digit, construct the full number if (Character.isDigit(c)) { n = n * 10 + (c - '0'); } // if the current character is a plus operator else if (c == '+') { // include the number before it in the result result += sign * n; // reset the number n = 0; // '+' would not affect the sign within the parentheses sign = stack.peek(); } // if the current character is a minus operator else if (c == '-') { // include the number before it in the result result += sign * n; // reset the number n = 0; // '-' would negate the sign within the parentheses sign = stack.peek() * -1; } // if the current character is an opening brace, push the sign to the stack else if (c == '(') { stack.push(sign); } // if the current character is a closing brace, pop the sign from the stack else if (c == ')') { stack.pop(); } } // add the last number and return the result result += sign * n; return result; } public static void main(String[] args) { String exp = "-10+(5+(12+8)-2)+1"; System.out.println(eval(exp)); } } |
Output:
14
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from collections import deque def eval(exp): result = 0 n = 0 # stores the last number sign = 1 # sign is 1 for positive and -1 for negative # take a stack to store the sign stack = deque() stack.append(sign) # do for each character for c in exp: # if the current character is a digit, construct the full number if c.isdigit(): n = n * 10 + (ord(c) - ord('0')) # if the current character is a plus operator elif c == '+': result += sign * n # include the number before it in the result n = 0 # reset the number sign = stack[-1] # '+' would not effect the sign within () # if the current character is a minus operator elif c == '-': result += sign * n # include the number before it in the result n = 0 # reset the number sign = stack[-1] * -1 # '-' would negate the sign within () # if the current character is an opening brace, push the sign to the stack elif c == '(': stack.append(sign) # if the current character is a closing brace, pop the sign from the stack elif c == ')': stack.pop() # add the last number and return the result result += sign * n return result if __name__ == '__main__': exp = '-10+(5+(12+8)-2)+1' print(eval(exp)) |
Output:
14
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the length of the expression.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)