BUPT-homework/semester3/pset1/7-2-Infix-to-Postfix-Conversion.cpp

// Convert the infix expression to postfix expression.
#include <cctype>
#include <cstdio>
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int prec(char ch) {
  if (ch == '+' || ch == '-') {
    return 0;
  } else if (ch == '*' || ch == '/') {
    return 1;
  } else {
    // the precidence is the lowest, to make sure it stays in the stack.
    // calculate stuff outside the paren last
    return -1; 
  }
}

void printEval(string &postfix) {
  stack<double> st;
  double l, r;
  double ans;
  for (char ch : postfix) {
    if (isdigit(ch)) {
      st.push(ch - '0');
    } else {
      r = st.top();
      st.pop();
      l = st.top();
      st.pop();
      if (ch == '+') {
	ans = l + r;
      } else if (ch == '-') {
	ans = l - r;
      } else if (ch == '*') {
	ans = l * r;
      } else if (ch == '/') {
	ans = l / r;
      }
      st.push(ans);
    }
  }
  printf("%.2lf\n", st.top());
}

void printFix(string &postfix) {
  for (char ch : postfix) {
    printf("%c ", ch);
  }
}

int main(void) {
  string input;
  cin >> input;

  stack<char> st;
  string postfix;

  for (char ch : input) {
    if (isdigit(ch)) {
      postfix.push_back(ch);
    } else {
      // if is not a digit
      if (ch == '(') {
        st.push(ch);
      } else if (ch == ')') {
        while (st.top() != '(') {
          postfix.push_back(st.top());
          st.pop();
        }
        st.pop();
      } else {
        // a operand
        while (!st.empty() && prec(ch) <= prec(st.top())) {
          postfix.push_back(st.top());
          st.pop();
        }
        st.push(ch);
      }
    }
  }

  while (!st.empty()) {
    postfix.push_back(st.top());
    st.pop();
  }

  printEval(postfix);
  printFix(postfix);

  return 0;
}