逆波兰式和计算器

缘起

邓俊辉的数据结构第四章的例子. 需求是

(1+2*3)-4 需要求值, 并且输出其逆波兰式.

分析

所谓逆波兰式(缩写是RPN)指的是

123*+4-

wtf? 这是啥? 如果你让小学生算这个表达式，他分分钟叼死你.

那为什么要搞个这么别扭的逆波兰式呢? 如果你知道逆波兰式对于计算机有多友好你就知道为什么要有这个了.

计算机根据逆波兰式计算的过程只需要一个操作数栈即可（存储参与运算的数值用的栈）, 计算机从左至右扫描上述逆波兰式,

1 来了–>入栈，栈中1

2 来了–>入栈，栈中 1 2

3 来了–>入栈, 栈中 1 2 3

*来了 –> 弹栈，因为 * 是二元运算符, 所以弹栈2次, 其中栈顶是第二元操作数，次顶是第一元操作数, 这种规定放在满足交换率的运算符+和*上可能没什么, 但是放在不满足交换律的-上就有作用了. 2*3=6, 然后再次入栈. 则栈中

1 6

+来了, 弹栈，同上面的*. 栈中7

4来了, 入栈，栈中 7 4

-来了, 弹栈2次, 7-4=3 入栈，栈中最后的计算结果就是原表达式的结果3

所以，RPN虽然反人类，但是对于计算机是相当友好的. 注意，RPN的特点如下

1. 逆波兰式没有括号.
2. 运算符来了就能直接计算的. 弹栈次数和运算符的元数有关.
3. 操作数的顺序和人类看得懂的表达式一致.
4. 操作符的顺序和人类看得懂的表达式未必一致. 这与运算符的优先级有关.

而对于人类可以看懂的表达式计算机怎么计算呢?

对于人类可以阅读的计算表达式, 代价是需要两个栈. 一个存储操作数S1，一个存储操作符S2. 只要操作符栈没空（操作符栈先入一个 \0 作为头部哨兵, 最后表达式字符串有一个 \0（这是C\C++对于字符串的处理）），运算就要继续. 遇到操作数就压栈S1, 并且写入RPN（这与RPN的特点3一致）,遇到操作符要分情况

1. 如果当前操作符比S2栈顶的操作符优先级高, 则不急着计算, 要延迟, 因为后面可能出现优先级更高的运算符. 所以不能现在着急计算, 既然当下不能计算, 所以就不能写入RPN（这与RPN的特点2一致），①将操作符压栈，②并继续读取表达式的下一个字符.
2. 如果优先级一致（只有左括号和右括号优先级一致，伊始就放入操作符栈的 哨兵\0和结束时候放进去的哨兵 \0 之间才相等, ps: 为什么要放进去 \0? 试想一下, 一开始就只有2个数字和一个操作符, 比如1+2, 则1 2 在S1中, + 在S2中, 如果不来一个 \0 作为尾部哨兵的话, 则1+2的计算怎么启动呢?），则①脱括号（即操作符弹栈）,②再继续读取下一个表达式的字符.
3. 如果优先级比S2栈顶的操作符低, 则就可以计算了.① 立马根据栈顶的操作符的元数弹栈,操作符弹栈之后 然后计算结果再次入栈. 注意，并不会继续读取下一个表达式字符, 因为不晓得会不会继续消掉操作符.

综上论述 我们给出如下算法

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <cstdlib>

using namespace std;
// 以(1+2*3)-4 为例子
#define N_OPTR 9 //运算符总数
typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合 加减乘除、幂、阶乘、左括号、有括号、结束符 共计9个
const char pri[N_OPTR][N_OPTR] = { //运算符优先等级 [栈顶] [当前]
	/* |-------------------- 当前 运 算 符 --------------------| */
	/*          +    -    *    /    ^    !    (    )   \0 */
	/* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
	/* |  - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
	/* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
	/* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
	/* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
	/* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
	/* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
	/* |  ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
	/* --\0 */ '<', '<', '<', '<', '<', '<', '<', ' ', '='
};

// 自己封装栈操作——观察、取数 二连弹
template<typename T>
T peer(stack<T>& stk) {
	T t = stk.top();
	stk.pop();
	return t;
}

// 读入数字
void readNumber(char *&p, stack<float>& stk) {
	stk.push((float)(*p - '0'));
	while(isdigit(*(++p))) {
		stk.push(peer(stk) * 10 + (*p - '0'));
	}
	// 如果是整数
	if(*p != '.') {
		return;
	}
	float fraction = 1;
	while(isdigit(*(++p))) {
		// 小数部分
		stk.push(peer(stk) + (*p - '0') * (fraction /= 10));
	}
}

// 将操作数oprnd添加至RPN的末尾
void append(char *rpn, float oprnd) {
	char buf[64];
	if(oprnd != (float)(int)oprnd) { // 如果是浮点格式
		sprintf(buf, "%.2f\0", oprnd);
	} else {
		sprintf(buf, "%d\0", (int)oprnd);
	}
	// RPN加长
	strcat(rpn, buf);
}

// 根据op 求出编号
Operator optr2rank(char op) {
	switch(op) {
	case '+':
		return ADD;
	case '-':
		return SUB;
	case '*':
		return MUL;
	case '/':
		return DIV;
	case '^':
		return POW;
	case '!':
		return FAC;
	case '(':
		return L_P;
	case ')':
		return R_P;
	case '\0':
		return EOE;
	default:
		// 异常退出，未知运算符
		exit(-1);
	}
}

// 比较两个运算符之间的优先级，p1是栈顶的, p2是当前的
char orderBetween(char p1, char p2) {
	return pri[optr2rank(p1)][optr2rank(p2)];
}

// 将运算符接至RPN末尾
void append(char *rpn, char optr) {
	// 原rpn长度
	int len = strlen(rpn);
	// 接上
	rpn[strlen(rpn)] = optr;
	rpn[len + 1] = 0;
}

// 阶乘
float fac(int n) {
	long long ret = 1;
	while(n--) {
		ret *= n;
	}
	return ret;
}

// 二元计算
float eval(float pOpnd1, char op, float pOpnd2) {
	switch(op) {
	case '+':
		return pOpnd2 + pOpnd1;
	case '-':
		return pOpnd2 - pOpnd1;
	case '*':
		return pOpnd2 * pOpnd1;
	case '/':
		return pOpnd2 / pOpnd1;
	case '^':
		exit(-1);
	}
}



// 计算器, S是表达式, RPN 是生成的逆波兰式(注意, 逆波兰式是不包含括号的)
// 其实最好的理解算法的方式就是纸上写一个小例子进行模拟, 例如 (1+2*3)-4, 它的逆波兰就是 123*+4-
// 在纸上写了之后你就会明白为什么上面的比较矩阵要那么写, 而且为什么要有 \0 这种哨兵的存在, 如果没有哨兵的话, 则最后4入栈, 也无法结束整个运算
// 而且你也明白为什么对于低优先级的运算符进来, S不继续往后走了, 因为它要等着消消消
float calc(char *S, char *&RPN) {
	// 操作数栈
	stack<float> oprnd;
	// 操作符栈
	stack<char> optr;
	// 先放进休止符入操作符栈
	optr.push('\0');
	// 只要操作符栈不空
	while(!optr.empty()) {
		// 如果当前的字符是数字
		if(isdigit(*S)) {
			// 读入这个数字进入操作数栈
			readNumber(S, oprnd);
			// 将操作数写入逆波兰表达式（逆波兰式由数字+操作符构成）
			append(RPN, oprnd.top());
		} else { // 如果当前字符为操作符的话
			// 比较两者的优先级
			switch(orderBetween(optr.top(), *S)) {
				// 当前运算符的优先级比栈顶运算符的优先级更高, 则需要延迟计算，也不要急于入rpn. 因为这个运算符并不是立马要参与计算的运算符, rpn中的运算符都是按照顺序进行的运算符
			case '<':
				optr.push(*S);
				// 继续读取表达式的下一个字符, 当前操作符不会写入逆波兰，因为逆波兰的都是即读即算的
				S++;
				break;
				// 当前运算符的优先级和栈顶运算符的优先级相等 这种情况只存在于当前运算符是右括号或者结束符的时候
			case '=':
				// 脱括号
				optr.pop();
				// 接收下一个字符
				S++;
				break;
				// 当前运算符的优先级比栈顶运算符的优先级低, 则可以计算了;
			case '>':
				// 操作符栈弹栈
				char op = peer(optr);
				// 追加到rpn  因为, 逆波兰式的操作符是按顺序进行的
				append(RPN, op);
				if('!' == op) { // 一元运算符
					// 操作数栈弹栈
					float pOpnd = peer(oprnd);
					// 计算出结果，重新入栈
					oprnd.push(fac((int)pOpnd));
					// 如果是二元运算符
				} else {
					// 弹栈2个操作数
					float pOpnd1 = peer(oprnd);
					float pOpnd2 = peer(oprnd);
					// 二元计算之后入再操作数栈
					oprnd.push(eval(pOpnd1, op, pOpnd2));
				}
				break;
			}
		}
	}
	// 最后弹栈的就是计算结果, 此时rpn中也就是逆波兰式
	return peer(oprnd);
}


int main() {
	char express[1005];
	cin.getline(express, 1005);
	char rpn[1005] = {'\0'};
	char *p = rpn;
	// 打印计算结果
	printf("%.2f\n",calc(express, p));
	// 打印逆波兰表达式
	printf("%s\n", rpn);
	return 0;
}