Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value. 
The integer division should truncate toward zero.

Example:

Input:  str="3+2*2"
Output: 7

Approach

Java

import java.util.Stack;

public class BasicCalculatorII {
    public static void main(String[] args) {
        String str = "-2+ 1";
        System.out.println(calculate(str));
    }

    // function to find the precedence of
    // the operators
    static int precedence(char op) {
        if (op == '*' || op == '/')
            return 1;
        if (op == '+' || op == '-')
            return 0;
        return -1;
    }

    // function to solve the given equation
    static int calculate(String s) {

        // operator stack
        Stack<Character> op = new Stack<>();
        // value stack
        Stack<Integer> val = new Stack<>();
        int n = s.length();

        // iterate till the length of string
        for (int i = 0; i < n; i++) {

            // if space then continue
            if (s.charAt(i) == ' ')
                continue;

            // if open bracket then push into the
            // operator stack
            else if (s.charAt(i) == '(')
                op.push(s.charAt(i));

            // if digit
            else if (Character.isDigit(s.charAt(i))) {
                int x = 0;

                // find the complete number till we get digits
                while (i < n && Character.isDigit(s.charAt(i))) {
                    x = (x * 10) + (s.charAt(i) - '0');
                    i++;
                }

                // push into the value stack
                val.push(x);
                i--;
            }
            // if closing bracket
            else if (s.charAt(i) == ')') {

                // iterate till the operator top
                // is not open brack and operator stack is not
                // empty
                while (!op.isEmpty() && op.peek() != '(') {

                    // pop two values from value stack
                    int val1 = val.pop();
                    int val2 = val.pop();
                    // pop the operator from operator stack
                    char c = op.pop();

                    // if +
                    if (c == '+')
                        val.push(val2 + val1);

                    // if -
                    else if (c == '-')
                        val.push(val2 - val1);

                    // if *
                    else if (c == '*')
                        val.push(val2 * val1);

                    // if /
                    else
                        val.push(val2 / val1);
                }
                // if operator stack is not empty
                // then pop from operator stack
                if (!op.empty())
                    op.pop();
            } else {

                // now according to precendence
                while (!op.isEmpty() && precedence(op.peek()) >= precedence(s.charAt(i))) {
                    int val1 = val.pop();
                    int val2 = 0;
                    if (!val.isEmpty())
                        val2 = val.pop();
                    char c = op.pop();
                    if (c == '+')
                        val.push(val2 + val1);
                    else if (c == '-')
                        val.push(val2 - val1);
                    else if (c == '*')
                        val.push(val2 * val1);
                    else
                        val.push(val2 / val1);
                }
                op.push(s.charAt(i));
            }
        }

        // now while operator stack is not
        // empty
        while (!op.isEmpty()) {
            int val1 = val.pop();
            int val2 = 0;
            if (!val.isEmpty())
                val2 = val.pop();
            char c = op.pop();
            if (c == '+')
                val.push(val2 + val1);
            else if (c == '-')
                val.push(val2 - val1);
            else if (c == '*')
                val.push(val2 * val1);
            else
                val.push(val2 / val1);
        }

        // return the final result
        return val.peek();
    }

}

C++

#include <bits/stdc++.h>
using namespace std;
int precedence(char op)
{
        if(op=='*'||op=='/')
              return 1;
        if(op=='+'||op=='-')
              return 0;
        return -1;
}
int calculate(string s) 
{
        stack<char> op;
        stack<int> val;
        int n=s.size();
        for(int i=0;i<n;i++)
         {
            if(s[i]==' ')
                  continue;
            else if(s[i]=='(')
                  op.push(s[i]);
            else if(isdigit(s[i]))
            {
                int x=0;
                while(i<n&&isdigit(s[i]))
                {
                    x=(x*10)+(s[i]-'0');
                    i++;
                }
                val.push(x);
                i--;
            }
          else if(s[i]==')')
           {
              while(!op.empty()&&op.top()!='(')
              {
                  int val1=val.top();
                  val.pop();
                  int val2=val.top();
                  val.pop();
                  char c=op.top();
                  op.pop();
                  if(c=='+')
                        val.push(val2+val1);
                  else if(c=='-')
                         val.push(val2-val1);
                  else if(c=='*')
                         val.push(val2*val1);
                  else
                        val.push(val2/val1);
              }
              if(!op.empty())
                    op.pop();
           }
          else
          {
              while(!op.empty()&&precedence(op.top())>=precedence(s[i]))
              {
                  int val1=val.top();
                  val.pop();
                  int val2=val.top();
                  val.pop();
                  char c=op.top();
                  op.pop();
                    if(c=='+')
                        val.push(val2+val1);
                  else if(c=='-')
                         val.push(val2-val1);
                  else if(c=='*')
                         val.push(val2*val1);
                  else
                        val.push(val2/val1);
              }
              op.push(s[i]);
          }
         }
         while(!op.empty())
              {
                  int val1=val.top();
                  val.pop();
                  int val2=val.top();
                  val.pop();
                  char c=op.top();
                  op.pop();
                    if(c=='+')
                        val.push(val2+val1);
                  else if(c=='-')
                         val.push(val2-val1);
                  else if(c=='*')
                         val.push(val2*val1);
                  else
                        val.push(val2/val1);
              }
      return val.top();
}
int main()
{
  string str="3+2*2";
  cout<<calculate(str);
  return 0;
}