#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <map>
#include <string.h>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <cassert>

// 1. Part 1 can create correct post-fix expression from the input
// (The operators are addition and multiplication.
// All the operands are positive integers between 1 and 9)                                           (10%)

// 2. Part 2 can evaluate the simple post-fix expression correctly
// (The operators are addition and multiplication,
// all the operands are positive integers between 1 and 9.
// In the post-fix expression, all the operands and operators are separated by a “ ”.) (10%)

// 3. The operands can be any positive integers.           (5%)
// 4. The operands can be negative integers.               (5%)
// 5. The operands can be float numbers.                   (5%)
// 6. The operators can be “-, /, ^, (, )”.                (5%)

// 2. pseudo code of the algorithm
// convert to postfix expression use stack,
// 1. if it is an operand, add to postfix,
// 2. if it is an operator,
//      2.1 if it is the first operator, push into `s` stack
//      2.2 if `s` stack already got element, compare the weight of opreators
//      2.3 pop `s` stack until the top most one got smaller precedence
// 3. if it is a bracket, push into stack `s`,
// 3. if it is a closing bracket, pop all element from `s` stack back to postfix,
// else return the result

/**
 * check if a string is a number
 * @param str_test the string to check
 * @return true if the string is a number, false otherwise
 */
bool checkIsNumber(std::string &str_test)
{
  bool output = true;

  // check if the string is longer than 1 character
  if (str_test.length() > 1)
  {
    // check each character in the string
    for (auto &c : str_test)
    {
      // if the character is not a digit, a dot or a minus sign
      if (!(('1' <= c && c <= '9') || c == '.' || c == '-'))
      {
        // set the output to false
        output = false;
        // break the loop
        break;
      }
    }
  }
  else
  {
    // if the string is only one character long
    char c = str_test[0];
    // if the character is not a digit
    if (!(('1' <= c && c <= '9')))
    {
      // set the output to false
      output = false;
    }
  }

  return output;
}

// 1. Part 1 can create correct post-fix expression from the input
std::queue<std::string> infixToPostfix(const std::string &infix)
{
  std::queue<std::string> output;
  std::stack<std::string> ss;
  std::queue<std::string> q_postfix;
  std::string postfix_temp;
  std::map<std::string, int> q_precedence = {{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}, {"(", 0}, {"^", 3}};
  std::stack<char *> sc;
  std::queue<std::string> q;

  const char s_delimit[2] = " ";
  char *token;
  // seperated by delimiter space
  token = strtok(const_cast<char *>(infix.c_str()), s_delimit);
  while (token != NULL)
  {
    q.push(token);
    token = strtok(NULL, s_delimit);
  }

  while (!q.empty())
  {
    std::string temp = q.front();
    q.pop();

    if (checkIsNumber(temp))
    {
      q_postfix.push(temp);
    }

    // 其實括號入面同括號出面嘅數你當佢兩條式計就得
    else if (temp.compare("(") == 0)
    {
      // 2. if '(', push to stack
      ss.push(temp);
    }

    // 咁佢呢度關括號呀嘛,
    // 咁佢咪會由個 stack 嗰度 port 返曬啲operator出嚟囉, 1+4*5 變咗 145*+
    // 永遠解開 operator都係會向由左向右
    else if (temp.compare(")") == 0)
    {
      while (!ss.empty() && ss.top() != "(")
      {
        q_postfix.push(ss.top());
        ss.pop();
      }

      if (!ss.empty())
        ss.pop(); // pop '('
    }
    else
    {
      // 4. if operator, pop operators with greater or equal precedence
      // 比較兩個 operand 之間個先後次序, 數字大嘅計先
      while (!ss.empty() && q_precedence[temp] <= q_precedence[ss.top()])
      {
        q_postfix.push(ss.top());
        ss.pop();
      }
      ss.push(temp); // push current operator
    }
  }

  // 5. pop last operator
  while (!ss.empty())
  {
    q_postfix.push(ss.top());
    ss.pop();
  }

  return q_postfix;
}

float evaluatePostfix(std::queue<std::string> &postfix)
{
  std::stack<float> s;
  std::string element = postfix.front();

  std::cout << "Corresponding postfix expression: ";

  while (!postfix.empty())
  {
    // 獨立 pop 番佢出嚟
    std::string element = postfix.front();
    postfix.pop();
    std::cout << element << ' ';

    if (checkIsNumber(element))
    { // 1. if operand, push to stack
      s.push(std::stof(element));
    }
    else
    {
      // 如果見到係operator, 攞返嗰兩粒數字出嚟計計佢
      float op2 = s.top();
      s.pop();
      float op1 = s.top();
      s.pop();

      switch (element[0])
      {
      case '+':
        s.push(op1 + op2);
        break;
      case '-':
        s.push(op1 - op2);
        break;
      case '*':
        s.push(op1 * op2);
        break;
      case '/':
        s.push(op1 / op2);
        break;
      case '^':
        float temp = op1;
        for (float i = 0; i < op2 - 1; i++)
        {
          op1 = op1 * temp;
        }
        s.push(op1);
        break;
      }
    }
  }

  std::cout << std::endl;

  return s.top();
}

int main()
{
  std::queue<std::string> q_temp;
  std::string infix;
  float result = 0;

  infix = "1 + 2";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(result == 3);

  // 3. The operands can be any positive integers.           (5%)
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "1 + 2 - 3 + 4 - 5 + 6 - 7 + 8 - 9";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(result == -3);

  // 3. The operands can be any positive integers.           (5%)
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "1 + 2 - 3 * 4 / 5 + 6 - 7 * 8 + 9";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(std::abs(result - -40.4) < 0.0001);

  // 4. The operands can be negative integers.               (5%)
  infix = "-1 + 2";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(result == 1);

  // 4. The operands can be negative integers.               (5%)
  infix = "1 + -2";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(result == -1);

  // 4. The operands can be negative integers.               (5%)
  infix = "-1 + -2";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(result == -3);

  // 5. The operands can be float numbers.                   (5%)
  infix = "1.1 + 2.1";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(std::abs(result - 3.2) < 0.001);

  // 5. The operands can be float numbers.                   (5%)
  // 4. The operands can be negative integers.               (5%)
  infix = "-1.1 + 2.3";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(std::abs(result - 1.2) < 0.001);

  // 5. The operands can be float numbers.                   (5%)
  infix = "1.1 * 6";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(std::abs(result - 6.6) < 0.001);

  //
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "1 + 2 ^ 3";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(result == 9);

  //
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "( 1 + 4 ) * 5";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  assert(result == 25);
  std::cout << "result: " << result << std::endl;

  //
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "( 1 + 4 * 5 ) * 5";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  assert(result == 105);
  std::cout << "result: " << result << std::endl;

  //
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "( 1 + 4 * 5 ) - 2 * 5";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  assert(result == 11);
  std::cout << "result: " << result << std::endl;

  //
  // 6. The operators can be “-, /, ^, (, )”.                (5%)
  infix = "( 11 + 4 * 5 ) - 6 * 5";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  assert(result == 1);
  std::cout << "result: " << result << std::endl;

  //
  // 5. The operands can be float numbers.                   (5%)
  // 6. The operators can be “-, /, ^, (, )”.
  infix = "( 1.1 + 4 ) * 2";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  assert(std::abs(result - 10.2) < 0.001);
  std::cout << "result: " << result << std::endl;

  //
  // 5. The operands can be float numbers.                   (5%)
  // 6. The operators can be “-, /, ^, (, )”.
  infix = "1 + ( 1 + ( 1 + 2 ^ 3 ) * 3 ^ 2 ) * 2";
  std::cout << "e.g. " << infix << std::endl;
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;
  assert(std::abs(result - 165) < 0.001);

  std::cout << "Enter an arithmetic expression: ";
  std::getline(std::cin, infix);
  q_temp = infixToPostfix(infix);
  result = evaluatePostfix(q_temp);
  std::cout << "result: " << result << std::endl;

  std::cout << "done" << std::endl;

  return 0;
}