#include <Arduino.h>

// Declaration for infix to postfix conversion and evaluation
class CharStack {
private:
  char* arr;
  int capacity;
  int top;
public:
  CharStack(int size) : capacity(size), arr(new char[size]), top(-1) {}
  ~CharStack() { delete[] arr; }
  void push(char element) { if (top < capacity - 1) arr[++top] = element; }
  char pop() { return top >= 0 ? arr[top--] : '\0'; }
  char peek() { return top >= 0 ? arr[top] : '\0'; }
  bool isEmpty() { return top < 0; }
};

class FloatStack {
private:
  float* arr;
  int top;
public:
  FloatStack(int size) : arr(new float[size]), top(-1) {}
  ~FloatStack() { delete[] arr; }
  void push(float element) { arr[++top] = element; }
  float pop() { return arr[top--]; }
  bool isEmpty() const { return top < 0; }
};

String infixToPostfix(String infix);
int precedence(char op);
bool isOperator(char c);
float evaluatePostfix(const String& postfix);
String addZeroBeforeUnaryMinus(const String& infix);

void setup() {
  Serial.begin(9600);
  while (!Serial); // Wait for Serial to initialize

  Serial.println("Enter an infix expression:");
}

void loop() {
  // Check if data is available from the Serial Monitor
  if (Serial.available() > 0) {
    // Read the input expression from Serial Monitor
    String infix = Serial.readStringUntil('\n'); // Read the input until newline
    infix.trim(); // Remove any leading/trailing whitespace
    Serial.println("Infix: " + infix);

    // Convert to postfix
    String postfix = infixToPostfix(infix);
    Serial.println("Postfix: " + postfix);

    // Evaluate the postfix expression
    float result = evaluatePostfix(postfix);
    Serial.print("Result: ");
    Serial.println(result, 6); // Print result with 6 decimal places

    // Prompt the user to enter a new expression
    Serial.println("Enter another infix expression:");
  }
}

String addZeroBeforeUnaryMinus(const String& infix) {
  String modifiedInfix = "";
  bool lastWasOperatorOrStart = true; // True at the start or after an operator

  for (unsigned int i = 0; i < infix.length(); ++i) {
    char ch = infix[i];

    if (ch == '-' && lastWasOperatorOrStart) {
      modifiedInfix += "(0-"; // Start unary minus handling
      i++; // Move to the next character (the number or expression after '-')
      while (i < infix.length() && (isdigit(infix[i]) || infix[i] == '.')) {
        modifiedInfix += infix[i]; // Add the number directly after '-'
        i++;
      }
      i--; // Decrement to offset the loop's next increment
      modifiedInfix += ")"; // Close unary minus handling
    } else {
      modifiedInfix += ch; // Just copy the character
    }

    // Update the flag based on current character
    lastWasOperatorOrStart = isOperator(ch) || ch == '(';
  }
  return modifiedInfix;
}

String infixToPostfix(String infix) {
  infix = addZeroBeforeUnaryMinus(infix); // Preprocess the infix expression
  CharStack operatorStack(100); // Sufficient size for the stack
  String postfix = "";
  bool expectOperand = true; // Indicates we expect a number or unary operator next

  for (int i = 0; i < infix.length(); i++) {
    char currentChar = infix[i];

    if (isdigit(currentChar) || (currentChar == '-' && expectOperand)) {
      // Append the operand (or unary minus) to the postfix string
      if (currentChar == '-') {
        postfix += '0'; // Handle unary minus
        postfix += ' '; // Space before the unary minus operator
      }
      postfix += currentChar;
      while (i + 1 < infix.length() && (isdigit(infix[i + 1]) || infix[i + 1] == '.')) {
        postfix += infix[++i];
      }
      postfix += ' '; // Ensure there's a space after the operand
      expectOperand = false; // After a number, an operator is expected
    } else if (isOperator(currentChar)) {
      while (!operatorStack.isEmpty() && precedence(operatorStack.peek()) >= precedence(currentChar)) {
        postfix += operatorStack.pop();
        postfix += ' '; // Ensure there's a space after popping an operator
      }
      operatorStack.push(currentChar);
      expectOperand = true; // Expecting a number or unary minus after an operator
    } else if (currentChar == '(') {
      operatorStack.push(currentChar);
      expectOperand = true; // Unary minus can follow '('
    } else if (currentChar == ')') {
      while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
        postfix += operatorStack.pop();
        postfix += ' '; // Ensure there's a space after popping an operator
      }
      operatorStack.pop(); // Remove '(' from the stack
      expectOperand = false; // Flexible expectation after ')'
    }
  }

  // After the while loop that empties the operator stack
  while (!operatorStack.isEmpty()) {
    postfix += operatorStack.pop();
    postfix += ' '; // Ensure there's a space after popping the remaining operators
  }
  postfix.trim(); // Trim any trailing spaces
  return postfix; // Return the trimmed postfix expression
}

int precedence(char op) {
  switch (op) {
    case '+': case '-': return 1;
    case '*': case '/': return 2;
    default: return -1;
  }
}

bool isOperator(char c) {
  return c == '+' || c == '-' || c == '*' || c == '/';
}

float evaluatePostfix(const String& postfix) {
  FloatStack stack(50); // Assume a sufficiently large stack
  int i = 0;

  while (i < postfix.length()) {
    if (postfix[i] == ' ') {
      i++; // Skip spaces
      continue;
    }

    if (isOperator(postfix[i])) {
      // Perform operation since the character is an operator
      float val2 = stack.pop();
      float val1 = stack.pop();
      switch (postfix[i]) {
        case '+': stack.push(val1 + val2); break;
        case '-': stack.push(val1 - val2); break;
        case '*': stack.push(val1 * val2); break;
        case '/': 
          if (val2 != 0) {
            stack.push(val1 / val2); 
          } else {
            Serial.println("Error: Division by zero");
            return 0.0; // Default value for error
          }
          break;
      }
      i++;
    } else {
      // Parse number, potentially with a negative sign
      String numStr = "";
      while (i < postfix.length() && (isdigit(postfix[i]) || postfix[i] == '.' || (numStr.length() == 0 && postfix[i] == '-'))) {
        numStr += postfix[i++];
      }
      float num = numStr.toFloat();
      stack.push(num);
    }
  }
  return stack.pop(); // Final result should be the only number left on the stack
}