Skip to content

Instantly share code, notes, and snippets.

@alexnoz
Created March 20, 2020 20:20
Show Gist options
  • Save alexnoz/96a7480d5bf51d64b790a6d9e67e6a64 to your computer and use it in GitHub Desktop.
Save alexnoz/96a7480d5bf51d64b790a6d9e67e6a64 to your computer and use it in GitHub Desktop.
Misc C++ basic stuff (balanced parens, postfix evaluation, infix -> postfix convertion)
#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';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment