逆波兰表达式

• 可参照文章逆波兰表达式

算法分析

• 若当前字符是操作数，则压栈
• 若当前字符是操作符，则弹出栈中的两个操作数，计算后仍然压入栈中

C++代码实现

/*
后缀表达式（逆波兰表达式）
有效操作只有'+'、'-'、'*'、'/'，且操作数是整数
*/
#include<iostream>
#include<string>
#include<assert.h>
#include<cstring>

using namespace std;

#define OVERFLOW -2
#define OK 1
#define ERROR -1

typedef int Status;
typedef int SElemType;

typedef struct StackNode {
	SElemType data;
	struct StackNode* next;
}StackNode, * LinkStack;

// 链栈初始化
void InitStack(LinkStack& S) {
	S = NULL;
}

// 判断链栈是否为空
Status StackEmpty(LinkStack S) {
	if (S == NULL) return 1;
	else return 0;
}

// 得到栈顶元素
Status GetTop(LinkStack S, SElemType& e) {
	if (StackEmpty(S)) return ERROR;
	e = S->data;
	return OK;
}

// 判断栈中是否只有一个元素
bool IsOne(LinkStack S) {
	if (StackEmpty(S)) return false;
	LinkStack p;
	p = S;
	int i = 0;
	while (p) {
		i++;
		p = p->next;
	}
	if (i == 1) return true;
	else return false;
}

// 入栈
Status Push(LinkStack& S, SElemType e) {
	LinkStack p;
	p = new StackNode;
	if (!p) exit(OVERFLOW);
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}

// 出栈
Status Pop(LinkStack& S, SElemType& e) {
	if (StackEmpty(S)) return ERROR;
	LinkStack p;
	e = S->data;
	p = S;
	S = S->next;
	delete p;
	p = NULL;
	return OK;
}

// 判断是否为数字
bool IsNum(char ch) {
	if (ch > '0' && ch < '9')
		return true;
	return false;
}

Status f(const char* str, SElemType& e) {
//	const char* str = str.c_str();
	assert(str);  // 断言 参数
	int size = strlen(str);
	int i = 0;
	LinkStack S;
	InitStack(S);
	int temp = 0;
	for (; i < size; i++) {
		if (IsNum(str[i]))
			// 转换为数字
			temp = temp * 10 + str[i] - '0'; 
		else if (str[i] == ' ') {
			if (IsNum(str[i - 1])) {
				// 当前字符为空格，且前一个为数字，入栈
				Push(S, temp);
				temp = 0;
			}
		}
		else {
			if (IsOne(S)) {
				// 栈中只有一个元素
				cout << "表达式有误，无法计算！" << endl;
				return ERROR;
			}
			Pop(S, e);
			int a = e;  // 右操作数
			Pop(S, e);
			int b = e;  // 左操作数
			switch (str[i]) {
			case '+':
				Push(S, b + a);
				break;
			case '-':
				Push(S, b - a);
				break;
			case '*':
				Push(S, b * a);
				break;
			case '/':
				if (a == 0) {
					cout << "被除数为零，无法计算！" << endl;
					return ERROR;
				}
				else {
					Push(S, b / a);
					break;
				}
			}
		}

	}
	if (!IsOne(S)) {
		cout << "表达式操作数过多！" << endl;
		return ERROR;
	}
	else {
		Pop(S, e);
		e = e;
		return OK;
	}

}

int main()
{
	SElemType e;
	const char* str = "1 3 + 4 * 4 /";
	f(str, e);
	cout << "结果为: " << e;
	return 0;
}

结果为: 4