利用棧計算算數(shù)表達式的值

先將中綴表達式利用棧轉(zhuǎn)換為后綴表達式，然后再利用棧由后綴表達式計算算數(shù)表達式的值，具體代碼如下：

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <stack>

enum Type
{
	OP_NUM,
	OP_SYMBOL,
};

enum Operat
{
	ADD,
	SUB,
	MUL,
	DIV,
};

struct Cell
{
	Type _type;
	int _num;
};

//input = 1 + ((2 + 3) * 4) - 5;

//中綴到后綴
string topolishNotation(const char* input)
{
	stack<char> s1; //運算符
	stack<char> s2; //數(shù)字
	size_t iCount = 0;
	while (input[iCount] != '\0')
	{
		//是數(shù)字將其壓入s2
		if (input[iCount] >= '0'&& input[iCount] <= '9')
		{
			while (input[iCount] != '\0' && input[iCount] >= '0'&& input[iCount] <= '9')
			{
				s2.push(input[iCount++]);
			}
			s2.push(' ');
			--iCount; //最后會統(tǒng)一加1，所以先減一
		}

		//是運算符比較其與S1棧頂運算符的優(yōu)先級
		while (input[iCount] == '+' || input[iCount] == '-' ||
			input[iCount] == '*' || input[iCount] == '/')
		{
			//s1為空，或棧頂運算符為左括號“(”，則直接將此運算符入棧
			if (s1.empty() || s1.top() == '(')
			{
				s1.push(input[iCount]);
				break;
			}
			//否則，若優(yōu)先級比棧頂運算符的高，也將運算符壓入s1
			else if ((input[iCount] == '*' || input[iCount] == '/') &&
				(s1.top() == '+' || s1.top() == '-'))
			{
				s1.push(input[iCount]);
				break;
			}
			//否則，將S1棧頂?shù)倪\算符彈出并壓入到S2中，再次與S1中新的棧頂運算符相比較
			else
			{
				s2.push(s1.top());
				s1.pop();
			}
		}

		//如果是左括號“(”，則直接壓入S1；
		if (input[iCount] == '(')
		{
			s1.push(input[iCount]);
		}

		/*如果是右括號“)”，則依次彈出S1棧頂?shù)倪\算符，并壓入S2，
		*直到遇到左括號為止，此時將這一對括號丟棄；*/
		if (input[iCount] == ')')
		{
			while (s1.top() != '(')
			{
				s2.push(s1.top());
				s1.pop();
			}
			s1.pop(); //將'('也出棧
		}

		++iCount; //統(tǒng)一加一次
	}

	//將S1中剩余的運算符依次彈出并壓入S2；
	while (!s1.empty())
	{
		s2.push(s1.top());
		s1.pop();
	}

	string ret;
	while (!s2.empty())
	{
		ret.push_back(s2.top());
		s2.pop();
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

//后綴到數(shù)組
vector<Cell> StrBehindToVect(const string& strBehind)
{
	vector<Cell> call;
	size_t iCount = 0;
	while (strBehind[iCount] != '\0')
	{
		if (strBehind[iCount] >= '0' && strBehind[iCount] <= '9')
		{
			int ret = 0;
			while (strBehind[iCount] != '\0' && strBehind[iCount] >= '0' && strBehind[iCount] <= '9')
			{
				ret = ret * 10 + strBehind[iCount] - '0';
				++iCount;
			}
			call.push_back({ OP_NUM, ret });
			--iCount;
		}
		else if (strBehind[iCount] == '+')
		{
			call.push_back({ OP_SYMBOL, ADD });
		}
		else if (strBehind[iCount] == '-')
		{
			call.push_back({ OP_SYMBOL, SUB });
		}
		else if (strBehind[iCount] == '*')
		{
			call.push_back({ OP_SYMBOL, MUL });
		}
		else if (strBehind[iCount] == '/')
		{
			call.push_back({ OP_SYMBOL, DIV });
		}
		++iCount;
	}
	return call;
}

//計算值
int RPNCount(const vector<Cell>& array, size_t size)
{
	stack<int> val;
	for (size_t i = 0; i < size; ++i)
	{
		if (array[i]._type == OP_NUM)
		{
			val.push(array[i]._num);
		}
		else
		{
			int right = val.top();
			val.pop();
			switch (array[i]._num)
			{
			case ADD:
				val.top() += right;
				break;
			case SUB:
				val.top() -= right;
				break;
			case MUL:
				val.top() *= right;
				break;
			case DIV:
				if (right == 0)
				{
					throw(array[i]);
				}
				val.top() /= right;
				break;
			default:
				cout << "請輸入合法字符" << endl;
				exit(0);
			}/*switch*/
		}
	}
	return val.top();
}

int main()
{
	string strMid = "12 * (3 + 4) - 6 + 8 / 2";
	string strBehind = topolishNotation(strMid.c_str());
	vector<Cell> call = StrBehindToVect(strBehind);
	try
	{
		int ret = RPNCount(call, call.size());
		cout << ret << endl;
	}
	catch (Cell)
	{
		cout << "除數(shù)為0!" << endl;
	}
	system("pause");
	return 0;
}