Calculate the basic arithmetic expression as string

Problem Statement:

You are given a string, that has a valid expression.
You need to implement a basic calculator and evaluate it.
String will consist of ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.

Example

Input:
str = “1 + 1”

output: 2

Solution

We will use stack for this problem.

So based on the input, there are 5 different types of input available:

1. digit: It might be a single digit or consecutive digits
2. Positive integer “+1”
3. Negative integer “-1”
4. Opening brace “(“: When we encounter opening brace, we push the result and sign into the stack, then reset the result to 0 and calculate the new result with in the parenthesis.
5. Closing brace “)”: When we encounter closing brace, we pop 2 elements, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. Then we calculate the result.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int calculate(string s) 
{

    int result = 0;
    int sign = 1; //1 rep +ve -1 rep -ve
    int j = 0;
    int len = s.length();
    stack<int> stk;


    while(j<len)
    { 
        //get the sign of the number 
        if(s[j]=='+')
        {
            sign=1;
        }
        else if(s[j]=='-')
        {
            //we got a negative value
            sign=-1;
        }

        //check if it is a digit 
        else if(isdigit(s[j]))
        {
            //get the number 
            int num=s[j]-'0';

            //check if it is a consecutive digit
            while(j+1<len && isdigit(s[j+1]))
            {
                num = num*10+(s[j+1]-'0');
                j++;
            }

            //add the number and sign
            result += num*sign;
        }

        //check if it is a opening brace
        else if(s[j]=='(')
        {
            //we push the current result and current sign into the stack
            stk.push(result);
            stk.push(sign);
            result=0;
            sign=1;
        }
        else if(s[j]==')')
        {
            //get the last sign
            int xsign = stk.top();
            stk.pop();

            //get the last result
            int xresult = stk.top();
            stk.pop();

            //calculate the result
            result = result*xsign + xresult;

            //xsign will be the sign before the begin of parenthesis
        }
        j++;
    }
    return result;
}

int main() 
{

  string s =  "(1+(4+5+2)-3)+(6+8)";
  cout<<" The result is  "<<calculate(s)<<endl;

    return 0; 
}

Output:

The result is 23