C++ :: Get Variable's Name

How to print a variables name instead of its value? (not just by giving the name yourself)

This can be easily done with a #define pre-processor directive. As #define treats the preceding expression as cstring, it is possible to get the variables name as a string. Look below:

#include <stdio.h>

#define getVarName(varName,holder) sprintf(holder, "%s", #varName)

int main() {
    int var = 100; // just any type of identifier
    char name[100]; // it will get the variables name
    getVarName(var, name);
    puts(name);
    return 0;
}

It will print "var" instead of "100" or something other. I saw it years ago somewhere I can't remember now. Today, it suddenly struck me and I think it might be useful who knows when...

Maximum Matching (DFS)

Maximum bipartite matching in a bipartite graph

Although Hopcroft Karp is faster and smarter, this one is pretty simple to code specially in contest time and when the graph is relatively smaller. It uses a DFS subroutine to cut and establish matching and thus produces a maximum matching. This version of BPM takes the adjacency list of left side of the bipartite graph and updates the Left[] and Right[] arrays with their respective matches.

Here, in the DFS subroutine, there are two for loops, where, the first one checks for yet unestablished connections, and the second one is the recursive DFS step. These two steps could be written in a single loop and the condition modified as "( Right[v]==-1 || dfs(Right[v]) )", actually separating them increases performance by some factors, because, first time it checks all the unmatched nodes before going into DFS.

A sample C++ implementation:

#define SET(x) memset(x, -1, sizeof(x))
#define CLR(x) memset(x, 0, sizeof(x))
#define MAX 100

vector < int > edges[MAX];
bool visited[MAX];
int Left[MAX], Right[MAX];

bool dfs(int u) {
    if(visited[u]) return false;
    visited[u] = true;
    int len = edges[u].size(), i, v;
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(Right[v]==-1) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    for(i=0; i<len; i++) {
        v = edges[u][i];
        if(dfs(Right[v])) {
            Right[v] = u, Left[u] = v;
            return true;
        }
    }
    return false;
}

int match() {
    SET(Left);
    SET(Right);
    int i, ret = 0;
    bool done;
    do {
        done = true;
        CLR(visited);
        for(i=0; i<MAX; i++) {
            if(Left[i]==-1 && dfs(i)) {
                done = false;
            }
        }
    } while(!done);
    for(i=0; i<MAX; i++) ret += (Left[i]!=-1);
    return ret;
}

Notes: Here, edges[MAX] is the left side adjacency list, implemented with vector, Left[MAX] and Right[MAX] holds the matching and the procedure match() returns maximum matching. Pretty straight forward.

Expression Evaluation

Infix to Postfix transformation and evaluation

Here, I would like to share a java source for converting an Infix expression to a Postfix equivalent and evaluate the Postfix expression. Postfix is also known as "Reverse Polish Notation". If you want to know more about this algorithm, this will be helpful.

Here is a simple java implementation. (Oh, we could do it a lot easily in C++, but, actually it has a academic purpose as well). A few things to note:

• Fixed format of input, as this is just a demonstration. Do not use spaces.
• It doesn't check whether the given expression is consistent or not.
• No math error is checked here, you have to add it to your own.
• Check sample execution for more details.
• Only for binary operators +,-,*,/,%,^ and parenthesis ()

Java Source

//
// @author Zobayer
// @date May 10, 2010
//

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

//
// Demonstrates Expression evaluation process.
// Doesn't take care of wrong input,
// You need to handle that on your own.
//

public class Expression {

    // A sample main() method to demonstrate this process
    public static void main(String[] args) throws IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String expr;
        List<String> inFix, postFix;
        int result;

        while((expr = stdin.readLine())!=null) {
            expr = "(" + expr + ")";
            inFix = getInFix(expr);
            postFix = getPostFix(inFix);
            result = evaluate(postFix);
            System.out.println("Postfix form: " + postFix);
            System.out.println("Result: " + result);
        }
    }

    // Parse the input string and form an infix notation
    static List<String> getInFix(String expr) {
        List<String> list = new ArrayList<String>();
        int n, i;
        char ch;
        boolean hasInt;

        for(i = n = 0, hasInt = false; i < expr.length(); i++) {
            ch = expr.charAt(i);
            if(!isDigit(ch)) {
                if(hasInt) {
                    list.add("" + n);
                    n = 0;
                    hasInt = false;
                }
                list.add("" + ch);
            }
            else {
                n = n * 10 + (ch - 48);
                hasInt = true;
            }
        }
        
        return list;
    }

    // Enlist the tokens in a postfix notation
    static List<String> getPostFix(List<String> inFix) {
        List<String> list = new ArrayList<String>();
        Stack<String> oper = new Stack<String>();
        int i;
        char ch;
        String token, peek;

        for(i = 0; i < inFix.size(); i++) {
            token = inFix.get(i);
            ch = token.charAt(0);
            if(isDigit(ch)) list.add(token);
            else if(ch=='(') oper.push("" + ch);
            else if(ch==')') {
                while(!oper.empty()) {
                    peek = oper.pop();
                    if(peek.charAt(0)!='(') list.add(peek);
                    else break;
                }
            }
            else {
                while(!oper.empty()) {
                    peek = oper.peek();
                    if(peek.charAt(0)!='(' && preced(ch) <= preced(peek.charAt(0))) {
                        list.add(peek);
                        oper.pop();
                    }
                    else {
                        oper.push(token);
                        break;
                    }
                }
            }
        }
        
        return list;
    }

    // Evaluate the postfix notation passed as a list
    static int evaluate(List<String> postFix) {
        Stack<Integer> stack = new Stack<Integer>();
        int i, a, b;
        String token;
        char ch;

        for(i = 0; i < postFix.size(); i++) {
            token = postFix.get(i);
            ch = token.charAt(0);
            if(isDigit(ch)) stack.push(Integer.parseInt(token));
            else {
                b = stack.pop();
                a = stack.pop();
                switch(ch) {
                    case '+': a = a + b; break;
                    case '-': a = a - b; break;
                    case '*': a = a * b; break;
                    case '/': a = a / b; break;
                    case '%': a = a % b; break;
                    case '^': a = (int)Math.pow(a, b); break;
                }
                stack.push(a);
            }
        }
        
        return stack.pop();
    }

    // Provides operator precedence
    static int preced(char op) {
        if(op=='^') return 3;
        if(op=='*' || op=='/' || op=='%') return 2;
        if(op=='+' || op=='-') return 1;
        return 0;
    }

    // Checks if ch is a digit or not
    static boolean isDigit(char ch) {
        return (ch >= '0' && ch <= '9');
    }
}

Sample run

(3+8-90*36)*((((89-5%6+2^3-10-10-10)))-8)+100
Postfix form: [3, 8, +, 90, 36, *, -, 89, 5, 6, %, -, 2, 3, ^, +, 10, -, 10, -, 10, -, 8, -, *, 100, +]
Result: -174266
90+0
Postfix form: [90, 0, +]
Result: 90
6+763-67*2367-(54/234)
Postfix form: [6, 763, +, 67, 2367, *, -, 54, 234, /, -]
Result: -157820

The algorithm implemented here is pretty simple, so I guess I haven't made a mistake yet, but who knows? So please check it...