一、历史

逆波兰式表示法（Reverse Polish Notation, RPN）可以看作波兰表示法（PN）的一种逆向表示。后者最初由波兰数学家Jan Lukasiewicz在1920年提出，由此得名。

在波兰表示法中，每个操作符均在相应的操作数之前，这也是牛逼的Lisp采用的表达式风格。与此相对的，逆波兰式中，每个操作符都在其操作数之后，由此也得名“后缀表示法（Postfix）”

ps：还记得C/C++中的 op += opr么？

例如表达式（3-4）*5的逆波兰式为：3 4 – 5 *

而表达式3-4*5的逆波兰式为：3 4 5 * -

由此可以发现，逆波兰式中无需用括号来指定优先级，这是RPN一个非常有用的特点。

基于此特点，逆波兰式被提出用于解决表达式求值的问题。

ps：关于逆波兰式的更详细信息，请参看http://en.wikipedia.org/wiki/Reverse_Polish_notation

二、表达式预处理

应用RPN求解表达式的难点在于，如何将一个标准的表达式转换成RPN，即Infix to Postfix

对于词法分析器来说，生成RPN可以通过构造一个词法树，然后对其后序遍历。

但是对于简单的应用来说，使用堆栈就可以解决这个问题。

首先我们需要一个堆栈用于保存操作符，假设为s，那么相应算法描述如下：

1.碰到操作数，直接输出
2.碰到操作符op
如果op是( 则直接入栈s
如果op是) 那么s弹栈并输出，一直到弹出(
如果op是+-*/，那么
如果s为空 或者 top[s] == ( 或者 op的优先级高于top[s] 则 op入栈
否则 s弹栈并输出，接着重复上一步
如果表达式分析完毕后栈s不为空，将剩下的操作符全部输出

如此，Infix已经被转换成了Postfix

这里需要注意的是，为了能正确的应用此算法，一般将()的优先级设置为最高

Read the rest of this entry »

RT

好久没写Blog，写一篇凑凑数。

来自某个很无聊的“作业”，最初是让写一个简易科学计算器，为了避免做UI的麻烦，直接选择表达式求解的方式实现。

算法原型来自Lieo，经过部分改进后，支持负数和多重括号。

因为只是expression-evaluate的一个demo，所以没有写得太详细。

不支持小数，没有异常处理，包括除数为零。

这里说下算法：

首先需要有两个堆栈或者支持FILO性质的线性表（我用的是vector，便于调试时观察内部元素是否正确），分别保存操作数和操作符。

负数通过额外的符号位实现，并规定，操作符后面跟着的“-”表示负号，符号位逻辑求反。

遍历表达式时，如果碰到操作数，直接入操作数栈。碰到操作符op，先和操作符栈顶的元素比较优先级，如果优先级大于栈顶元素，入栈（如果操作符栈为空，直接入栈），否则取出操作符栈顶元素和操作数进行计算，一直到操作符栈空或者栈顶元素优先级小于操作符op。

对于括号特殊处理：

碰到“(”，直接入栈，碰到“)”，取出操作符栈和操作数栈计算，直到操作符栈中弹出“(”。

为了简化算法，表达式尾部需要有#符号充当哨兵元素，并规定#符号的优先级最小。

提供核心代码，全部代码请翻看SRC

#define pop(x) x.back(); \
				x.pop_back();

struct NumData
{
	NumData() : signal(false), pos(0)
	{
		wmemset(sz, L'\0', NUM_LEN);
	}

	enum{NUM_LEN = 10};
	wchar_t sz[NUM_LEN];
	bool signal;
	unsigned int pos;
};

int EvaluateExpression(wchar_t* pszExpression)
{
	stackOperand oprand;
	stackOperator oprator;
	bool isNumbericMode = true;
	NumData data;

	for (wchar_t* p = pszExpression; *p != NULL; ++p)
	{
		if (*p >= L'0' && *p <= L'9')
		{
			data.sz[data.pos++] = *p;
			isNumbericMode = false;
		}
		else if (L'-' == *p && isNumbericMode)
		{
			data.signal = !data.signal;
		}
		else	// pure operators
		{
			isNumbericMode = true;

			if (L'(' == *p)
			{
				oprator.push_back(*p);
			}
			else if (L')' == *p)
			{
				int num;

				if (data.pos)
				{
					num = FormatNumtoInt(data);
				}
				else
				{
					num = pop(oprand);
				}

				do
				{
					wchar_t op = pop(oprator);

					if (L'(' == op)
					{
						oprand.push_back(num);
						break;
					}
					else
					{
						int num2 = pop(oprand);
						num = Calculate(num2, num, op);
					}

				} while (true);
			}
			else	// operators except ( and )
			{
				int num;

				if (data.pos)
				{
					num = FormatNumtoInt(data);
				}
				else
				{
					num = pop(oprand);
				}

				do
				{
					if (oprator.empty() || (GetPriority(*p) > GetPriority(oprator.back())))
					{
						oprand.push_back(num);
						oprator.push_back(*p);

						break;
					}
					else
					{
						int num2 = pop(oprand);
						wchar_t op = pop(oprator);

						num = Calculate(num2, num, op);
					}

				} while (true);
			}

			//DumpStack(oprand);
		}
	}

	return oprand.back();
}

int FormatNumtoInt(NumData& data)
{
	assert(data.pos);

	int num = _wtoi(data.sz);
	num = data.signal ? -num : num;

	wmemset(data.sz, L'\0', NumData::NUM_LEN);
	data.pos = 0;
	data.signal = false;

	return num;
}

Download EvaluateExpression SRC

回家前在图书馆碰到了刘汝佳的《算法竞赛入门经典》，于是便借回来随手翻翻

个人实在不太喜欢这类风格的书，但是觉得某些题目不错，就随手做做，权当练习

1、位数

描述：输入一个不超过10^9的正整数（由输入者负责保证），输出它的位数。例如12735的位数是5.不要使用任何数学函数，只使用四则运算。

思路1：设接受的的n位整数为N，让i从1取到9（事实上，只要不发生溢出，可以取到上限），并令 k = N / 10^i，当k == 0时，则所求位数为i。算法复杂度为O(n)

int QueryDigit(int nNum)
{
    int nDigit, nDiv;

    for (nDigit = 1, nDiv = 10; nNum / nDiv; ++nDigit)
    {
        nDiv *= 10;
    }

    return nDigit;
}

思路2：查表法。很容易想到，每个数所在的位数区间都是确定的。比如12735在10000～99999这个区间范围内。而这个区间范围内的数都是5位。查表法需要写较多的代码，但是运行起来速度会快得多，不过只有在要查询的数字比较多的情况下才能体现。易知，复杂度为O(1)

int QueryDigit(int nNum)
{
    int DigitTable[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int nDigit;

    // a long long if statement
    if (0 <= nNum && nNum < 10)
    {
        nDigit = DigitTable[0];
    }
    else if (10 <= nNum && nNum < 100)
    {
        nDigit = DigitTable[1];
    }
    else if (100 <= nNum && nNum < 1000)
    {
        nDigit = DigitTable[2];
    }
    else if (1000 <= nNum && nNum < 10000)
    {
        nDigit = DigitTable[3];
    }
    else if (10000 <= nNum && nNum < 100000)
    {
        nDigit = DigitTable[4];
    }
    else if (100000 <= nNum && nNum < 1000000)
    {
        nDigit = DigitTable[5];
    }
    else if (1000000 <= nNum && nNum < 10000000)
    {
        nDigit = DigitTable[6];
    }
    else if (10000000 <= nNum && nNum < 100000000)
    {
        nDigit = DigitTable[7];
    }
    else
    {
        nDigit = DigitTable[8];
    }

    return nDigit;
}

2、韩信点兵

描述：相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只要掠一眼排尾的人数就知道总人数。输入3个非负整数a,b,c，表示每种队形排尾人数（a<3,b<5,c<7），输出总人数的最小值。

思路1：题目实质是求x=3*k1+a = 5*k2 + b = 7*k3 + c。可以通过令x从1开始进行尝试，第一个符合的数就是所求的数。分析可知，算法的复杂度是O(n)，这里的n只与所求数有关。

但事实上，存在复杂度为O(1)的算法。因为此题可以通过公式计算得到。

思路2：这道题在数论上颇有名气，其本质是求线性同余方程组的解。解法最早由宋朝秦九韶提出，并被国外数学家冠以“中国剩余定理”

ps：这本号称入门级的算竞赛辅导书（似乎还是面向中学生）居然会出现线性同余方程组求解的问题，表示这让我很诧异。

关于“中国剩余定理”的详细说明和分析将在未来几天内（起码得等我到家）完成。

由“中国剩余定理”可以得到韩信点兵问题的通解公式

知道了公式，代码就显得极其简单
Read the rest of this entry »