#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;

//based on the provided test cases I made the below assumptions:
//1. the expression is valid
  //i.e. we only see correct paranthesis and operators configurations and valid letters (upper case)

//2. we can have spaces but not between letters of a Roman number:
  //i.e. "  II +    II   " is valid but "I I + II" is invalid

//3. while evaluating the expression from left to right, the partial results never over/under flow. as a result, the final result will fit into a 32 bit integer as well

//4. the Roman numbers are positive. i.e. we don't have II+-II

//5. empty expression string corresponds to 0

int romanToInt (string number){
  unordered_map <string , int> helper;
  helper["V"] = 5;
  helper["L"] = 50;
  helper["D"] = 500;
  helper["M"] = 1000;
  helper["I"] = 1;
  helper["X"] = 10;
  helper["C"] = 100;
  helper["IV"] = 4;
  helper["IX"] = 9;
  helper["XL"] = 40;
  helper["XC"] = 90;
  helper["CD"] = 400;
  helper["CM"] = 900;
  int num = 0;
  for (int i=0 ; i<(int)number.length() ; i++){
    string temp = i+1 < (int)number.length ()? number.substr(i,2) : "";
    if (temp != "" && helper.count(temp) != 0){
      num+= helper[temp];
      i++;
    }
    else
      num += helper[number.substr(i,1)];
  }
  return num;
}


//the numbers' stack contains positive or negative numbers. We just need to add up all of the values of the stack to get the result that corresponds to that stack.
int evaluateNumsStack (stack <int>& numbers){
  int res = 0;
  while (!numbers.empty()){
    res += numbers.top();
    numbers.pop();
  }
  return res;
}


unordered_set <char> operands = {'-' , '+' , '/' , '*'};
unordered_set <char> validLetters = {'I', 'V' , 'X', 'C' , 'L' , 'D' , 'M'};


int evaluate (string expression , int &index , stack <int>& numbers , char operand){
  //remove leading zeros, if any
  while (index < (int)expression.length() && expression[index] == ' ')
    index++;
  if (index == (int)expression.length()){
    return evaluateNumsStack(numbers);
  }
  if (operands.count(expression[index]) != 0){
    operand = expression[index];
    return evaluate (expression , ++index , numbers , operand);
  }

  if (expression[index] == ')'){
    int res = evaluateNumsStack (numbers);
    return res;
  }
  int currNum = 0;
  if (expression[index] == '('){
    stack <int> temp;
    currNum = evaluate (expression , ++index , temp , operand);
  }
  else{
    //Roman number
    int tail = index;
    while (tail < (int)expression.length() && validLetters.count(expression[tail]) != 0)
      tail++;
    currNum = romanToInt (expression.substr(index , tail-index));
    index = tail-1;
  }
  
  if (numbers.empty())
    numbers.push(currNum);
  else{
    if (operand == '*' || operand == '/'){
      int prevNum = numbers.top();
      numbers.pop();
      int res = operand == '*' ? prevNum * currNum : prevNum/currNum;
      numbers.push(res);
    }
    else{
      currNum = operand == '-' ? -currNum : currNum;
      numbers.push(currNum);
    }
  }
  return evaluate (expression , ++index , numbers, operand);
}
int solution (string expression){
  if (expression == "")
    return 0;
  stack <int> numbers;
  int index = 0;
  return evaluate (expression , index , numbers , ' ');
}
int main(){
    cout << solution("MMMCMXCIX - V + LXXXIX") << endl;
}