You are given a string that contain a basic expression, calculate the result. Solution in C++.

Example:

“ 1 + 3” = 4

Multiplication and division signs are not allowed. Only positive and negative numbers are allowed.

This problem can be solved with the help of stacks.

Before getting into the solution, let us understand the questions with additional examples:

“4 + 4 – 5” = 3
“( 5 + (6-3) + 7)” = 15

So the input may include “(“ and “)” also. In order to evaluate these kind of expressions we take 2 stack variables. One stack variable is used to store the result. Another stack variable is used to hold “(“ value. Then we encounter “)” value, we can evaluate the result.

More details discussed in the code below:

Solution in C++:

#include<vector>
#include<iostream>
#include<stack>


using namespace std;


int calculate_string(string s) 
{
	stack<int> value; // to store the values like 4 + 5
	stack<int> oper;// to store open bracket "("

	int res = 0;// holds the final result 
	int sign = 1; // to check if the intermediate result is +ve or -ve

	for(int i = 0; i < s.size(); i++)
	{
		char c = s[i];
		if(isdigit(c)) // check if the current character is a digit
		{
			int num = c - '0'; // get the int value of that char 
			while(i + 1 < s.size() && isdigit(s[i + 1])) // this is to check for double or triple digits like "23", "345"
			{
				num = num * 10 + s[i + 1] - '0';
				i++;
			}
			res += num * sign;
		}

		else if(c == '+') 
			sign = 1;

		else if(c == '-') 
			sign = -1;

		else if(c == '(')
		{
			value.push(res);
			oper.push(sign);
			res = 0;
			sign = 1;
		}

		else if(c == ')')
		{
			res = res * oper.top();
			oper.pop();
			res += value.top();
			value.pop();
		}
	}
	return res;
}

int main()
{
	string str = "4 + 5";
	int result = calculate_string(str);
	cout<<" The value of "<< str << " is = "<<result;
}

Output:

The value of 4 + 5 is = 9