逆波蘭表達式也稱為后綴表達式，它將一個算數(shù)表達式不包含括號，運算符放在兩個運算對象的后面，所有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行，如下圖所示：

成都創(chuàng)新互聯(lián)于2013年成立，先為吉安等服務(wù)建站，吉安等地企業(yè)，進行企業(yè)商務(wù)咨詢服務(wù)。為吉安企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

在這里我們可以運用棧的特點來實現(xiàn)后綴表達式，思路如下：

1.首先當(dāng)遇到運算操作數(shù)時將其進行push操作；

2.當(dāng)遇到操作符是將此時的棧pop兩次，先取出的棧頂為右操作數(shù)；

3.執(zhí)行此方法到整個數(shù)組遍歷完。

我們在這里采用了數(shù)組來存儲后綴表達式中的元素，因為如果用字符串保存的話，首先解析字符串的時候會比較麻煩（既有數(shù)字還有字符），其次數(shù)組的大小控制也比較方便。

利用枚舉的方法將所要用到的運算符和操作數(shù)羅列出來

enum Type 
{
	OPERAND,  //操作數(shù)
	OPERATOR, //操作符
	ADD,//加法
	SUB,//減法
	MUL,//乘法
	DIV//除法
};

這樣方便我們后面的操作，可以在自由增減我們需要的運算方法。

#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;

enum Type 
{
	OPERAND,  //操作數(shù)
	OPERATOR, //操作符
	ADD,//加法
	SUB,//減法
	MUL,//乘法
	DIV//除法
};

struct Cell
{
	Type  _type;
	int  _value;
};

int CountRPN(Cell _a[], size_t _size)
{
	stack <int > s;
	for (size_t i = 0; i < _size; i++)
	{
		//如果是操作數(shù)進行push操作
		if (_a[i]._type == OPERAND)
		{
			s.push(_a[i]._value);
		}
		//如果是操作符則先將當(dāng)前棧頂元素取出
		//再取出另一個操作數(shù)做運算
		//注意：先取出的數(shù)為右操作數(shù)（在減法和除法中要區(qū)分開來）
		if (_a[i]._type == OPERATOR)
		{
			int  right = s.top();
			s.pop();
			int  left = s.top();
			s.pop();
			switch (_a[i]._value)
			{
			case ADD:
				s.push(left + right);
				break;
			case SUB:
				s.push(left - right);
				break;
			case MUL:
				s.push(left * right);
				break;
			case DIV:
				s.push(left / right);
				break;
			default:
				break;
			}
		}
	}
		return s.top();
}

int main()
{
	Cell RPNArray[] =
	{
		{ OPERAND, 12 },
		{ OPERAND, 3 },
		{ OPERAND, 4 },
		{ OPERATOR, ADD },
		{ OPERATOR, MUL },
		{ OPERAND, 6 },
		{ OPERATOR, SUB },
		{ OPERAND, 8 },
		{ OPERAND, 2 },
		{ OPERATOR, DIV },
		{ OPERATOR, ADD }
	};

	int ret = CountRPN(RPNArray, sizeof(RPNArray) / sizeof(RPNArray[0]));
	cout << ret << endl;

	system("pause");
	return 0;
}

運行結(jié)果如下：

寫在結(jié)尾：

本次編程需要注意理解逆波蘭表達式的意義，在保存元素時候注意選擇用數(shù)組而不是字符串。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

名稱欄目：數(shù)據(jù)結(jié)構(gòu)之用棧實現(xiàn)逆波蘭表達式-創(chuàng)新互聯(lián)
文章鏈接：http://jinyejixie.com/article48/hgsep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、域名注冊、定制開發(fā)、企業(yè)建站、網(wǎng)站設(shè)計公司、品牌網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)