Misc C++ basic stuff (balanced parens, postfix evaluation, infix -> postfix convertion)

misc.cpp

#include <iostream>
#include <stack>
#include <iomanip>
#include <map>
#include <cctype>
#include <cstdlib>

using namespace std;

#define SIZE(arr) (sizeof(arr) / sizeof((arr[0])))

bool contains(const char* arr, int size, char c) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == c) return true;
  }
  return false;
}

bool parensBalanced(const string& str) {
  static const char open[]  {'[', '(', '{'};
  static const char close[] {']', ')', '}'};
  static map<char, char> map = {
    {close[0], open[0]},
    {close[1], open[1]},
    {close[2], open[2]}
  };

  size_t parensAmount(SIZE(open));
  stack<char> stack;

  for (int i = 0; i < str.size(); i++) {
    const char c = str[i];

    if (contains(open, parensAmount, c)) {
      stack.push(c);
    } else if (contains(close, parensAmount, c)) {
      if (stack.empty() || stack.top() != map[c]) {
        return false;
      }
      
      stack.pop();
    } else {
      return false;
    }
  }

  return stack.empty();
}

int evaluateExpr(const char op, stack<int>& tokens) {
  int b = tokens.top(); tokens.pop();
  int a = tokens.top(); tokens.pop();

  int res;

  switch (op) {
    case '+':
      res = a + b;
      break;
    case '-':
      res = a - b;
      break;
    case '*':
      res = a * b;
      break;
    case '/':
      res = a / b;
      break;
  }

  return res;
}

int evaluatePostfix(const string& expr) {
  const string dlm = " ";
  int s = 0, e = expr.find(dlm);

  stack<int> tokens;

  while (e != string::npos) {
    const char *token = expr.substr(s, e - s).c_str();

    if (isdigit(token[0])) {
      tokens.push(atoi(token));
    } else {
      tokens.push(
        evaluateExpr(*token, tokens)
      );
    }

    s = e + dlm.length();
    e = expr.find(dlm, s);
  }

  return evaluateExpr(expr.back(), tokens);
}

bool isHigherPrecedence(char a, char b) {
  static map<char, char> opMap = {
    {'-', 1},
    {'+', 1},
    {'*', 2},
    {'/', 2}
  };
  return opMap[b] > opMap[a];
}

bool isOperator(char c) {
  static const char operators[] {'+', '-', '*', '/'};
  return contains(operators, SIZE(operators), c);
}

string infixToPostfix(const string& infixExpr) {
  string postfixExpr = "";
  stack<char> operators;

  for (const char& c : infixExpr) {
    if (c == ' ' && postfixExpr[postfixExpr.size() - 1] == ' ') {
      continue;
    }
    if (isdigit(c) || c == ' ') {
      postfixExpr += c;
    } else if (isOperator(c)) {
      while (operators.size() && operators.top() != '(' && isHigherPrecedence(c, operators.top())) {
        postfixExpr += operators.top();
        operators.pop();
      }
      operators.push(c);
    } else if (c == '(') {
      operators.push(c);
    } else if (c == ')') {
      while (operators.size() && operators.top() != '(') {
        postfixExpr += operators.top();
        operators.pop();
      }
      operators.pop();
    }
  }

  while (operators.size()) {
    postfixExpr += ' ';
    postfixExpr += operators.top();
    operators.pop();
  }

  return postfixExpr;
}

int main() {
  const string first = "[(])";
  const string second = ")(";
  const string third = "[()()[{}]]";

  std::cout << std::boolalpha;
  std::cout << first << " : " << parensBalanced(first) << '\n';
  std::cout << second << " : " << parensBalanced(second) << '\n';
  std::cout << third << " : " << parensBalanced(third) << '\n';

  const string infx = "2 + 2 * ( 2 - 37 ) / 5";
  const string postfix = infixToPostfix(infx);

  cout << postfix << '\n';
  cout << infx << " = " << evaluatePostfix(postfix) << '\n';
}