C++棧實現(xiàn)逆波蘭式的應(yīng)用

更新時間：2021年11月26日 09:19:43 作者：藍樂

逆波蘭式指的是操作符在其所控制的操作數(shù)后面的表達式。本文主要介紹了C++棧實現(xiàn)逆波蘭式的應(yīng)用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

一.定義

逆波蘭式，又稱后綴表達式，指的是操作符在其所控制的操作數(shù)后面的表達式。
舉個例子，1 + 2 * 3 - 4這個表達式是我們熟悉的中綴表達式，那么其所對應(yīng)的后綴表達式為：1 2 3 * + 4 -。
再來個復(fù)雜的例子：1 * (2 + 3) / 5 - 4 / 2其對應(yīng)的后綴表達式為：1 2 3 + * 5 / 4 2 / -（其中括號由于只是提升表達式優(yōu)先級的作用，因此不放入后綴表達式中）。

二.逆波蘭式的意義

為什么要將看似簡單的中綴表達式轉(zhuǎn)換為復(fù)雜的逆波蘭式，原因就在于這個簡單是相對我們?nèi)祟惖乃季S結(jié)構(gòu)來說的，對計算機而言中序表達式是非常復(fù)雜的結(jié)構(gòu)。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結(jié)構(gòu)。因為計算機普遍采用的內(nèi)存結(jié)構(gòu)是棧式結(jié)構(gòu)，它執(zhí)行先進后出的順序。

三.逆波蘭式的實現(xiàn)

1.方法

（1）中綴表達式轉(zhuǎn)化為后綴表達式

對于給出的中綴表達式，如何將其轉(zhuǎn)化為后綴表達式呢？
第一，若遇到操作數(shù)則直接輸出/存儲。
第二，遇到操作符，若此時棧為空或者操作符優(yōu)先級高于棧頂，則入棧。
第三，若操作符的優(yōu)先級低于或者等于棧頂，則出棧直至?？栈蛘邇?yōu)先級低于該操作符。
第四，遇到'(',其后的所有操作符（直至遇到')'）按上述操作入棧或出棧；當遇到')‘時，將'('頂上的所有操作符出棧。

在這里插入圖片描述

（2）由后綴表達式計算結(jié)果

第一，遇到操作數(shù)則入棧。
第二，遇到操作符則將棧頂?shù)膬蓚€操作數(shù)出棧，其中第一個數(shù)為右操作數(shù)，第二個數(shù)為左操作數(shù)。
第三，計算結(jié)果并將計算的結(jié)果入棧。
第四，最后棧頂?shù)慕Y(jié)果即為所計算的結(jié)果。

在這里插入圖片描述

2.代碼實現(xiàn)

#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

string trans(string& s)
{
	string operand;
	stack<char> Operator;
	int flag = 0;//記錄括號優(yōu)先級
	for (const auto& e : s)
	{
		if (e == '(')
		{
			Operator.push(e);
			flag = 1;
			continue;
		}
		if (e == ')')
		{
			flag = 0;
			while (Operator.top() != '(')
			{
				operand.push_back(Operator.top());
				Operator.pop();
			}
			Operator.pop();
			continue;
		}
		//操作符
		if (e == '+' || e == '-' || e == '*' || e == '/')
		{
			if (flag == 1)
			{
				if (Operator.top() == '(')
				{
					Operator.push(e);

				}
				else if ((e == '*' || e == '/') && (Operator.top() == '+' || Operator.top() == '-'))
				{
					Operator.push(e);
				}
				else//操作符的優(yōu)先級低于或等于棧頂操作符則出棧，直至遇到'('
				{
					while (Operator.top() != '(')
					{
						operand.push_back(Operator.top());
						Operator.pop();
					}
					Operator.push(e);
				}
			}
			else if (Operator.empty())//棧空就入棧
			{
				Operator.push(e);
			}
			//操作符的優(yōu)先級高于棧頂操作符，入棧
			else if ((e == '*' || e == '/') && (Operator.top() == '+' || Operator.top() == '-'))
			{
				Operator.push(e);
			}
			else//操作符的優(yōu)先級低于或等于棧頂操作符則出棧，直至?？栈蛘邇?yōu)先級高于棧頂操作符
			{
				while (!Operator.empty())
				{
					operand.push_back(Operator.top());
					Operator.pop();
				}
				Operator.push(e);
			}
		}
		//操作數(shù)
		else
		{
			operand.push_back(e);
		}
	}
	while (!Operator.empty())
	{
		operand.push_back(Operator.top());
		Operator.pop();
	}
	return operand;
}

int evalRPN(const string& s)
{
	stack<char> operand;
	int left = 0, right = 0;
	for (const auto& e : s)
	{
		if (e == '+' || e == '-' || e == '*' || e == '/')
		{
			switch (e)
			{
			case '+':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left + right);
				break;
			case '-':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left - right);
				break;
			case '*':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left * right);
				break;
			case '/':
				right = operand.top();
				operand.pop();
				left = operand.top();
				operand.pop();
				operand.push(left / right);
				break;
			}
		}
		else//操作數(shù)
		{
			operand.push(e - '0');
		}
	}
	return operand.top();
}

int RPN(const string& str)
{
	//1.中綴表達式轉(zhuǎn)化為后綴表達式
	string s(str);
	s = trans(s);
	//2.后綴表達式計算答案
	return evalRPN(s);
}

int main()
{
	string s("1*(2*3+5)/5-4/2");
	int ret = RPN(s);
	cout << "ret:" << ret << endl;
	return 0;
}

結(jié)果:

在這里插入圖片描述