用棧實作中綴表達式計算--逆波蘭表達式計算

剛開始學，請大佬們看一看有沒有啥問題。

"MyStack.h"

#pragma once
#include <iostream>
using namespace std;

template<class T>//結點 
class LinkNode
{
public:
	T data;//資料域
	LinkNode* next;//指針域
};

template<class T>
class LinkStack//棧
{
public:
	//初始化鍊棧
	LinkStack();
	//元素入棧
	void Push(T c);
	//元素出棧
	void Pop();
	//判斷棧是否為空
	bool isEmpty();
	//擷取棧頂元素，并用x接收
	T GetTop();
	//擷取棧長度
	int Length();
private:
	LinkNode<T>* HeadNode;//頭結點
	int len;
};

template<class T>
LinkStack<T>::LinkStack()
{
	HeadNode = new LinkNode<T>();
	HeadNode->next = NULL;
	len = 0;
}

//元素入棧
template<class T>
void LinkStack<T>::Push(T c)
{
	LinkNode<T>* p = new LinkNode<T>();
	p->data = c;
	p->next = HeadNode->next;
	HeadNode->next = p;
	++len;
}

//元素出棧
template<class T>
void LinkStack<T>::Pop()
{
	LinkNode<T>* p = HeadNode->next;
	if (p == NULL)
		return;
	HeadNode->next = p->next;
	delete p;
	--len;
}

//判斷棧是否為空
template<class T>
bool LinkStack<T>::isEmpty()
{
	LinkNode<T>* p = HeadNode->next;
	if (p == NULL)
		return true;
	else
		return false;
}

//擷取棧頂元素，并傳回
template<class T>
T LinkStack<T>::GetTop()
{
	if (!isEmpty())
		return HeadNode->next->data;
	else
		return NULL;
}

//擷取棧的長度
template <class T>
int LinkStack<T>::Length()
{
	return len;
}
           

 BracketMatch.h

#pragma once
#include <iostream>
using namespace std;

//判斷輸入的計算式括号是否合法
bool Bracket_isMatched(string str);
//輸入計算式，儲存在字元串str中
string EnString();
           

 BracketMatch.cpp

#include"MyStack.h"
#include"BracketMatch.h"
#include <iostream>
#include<string>
using namespace std;

//判斷括号是否合法
/*
	1.初始化一個鍊棧，周遊傳進來的字元串，
		遇到左括号則入棧，遇到右括号則:
			判斷棧是否為空，若為空則表明不比對；
			若棧不為空，将棧頂元素出棧，并檢驗是否與目前右括号比對；
	2.周遊完成後，檢驗棧是否為空，若為空則括号比對成功；否則，括号比對失敗
*/

//輸入計算式，儲存在字元串str中
string EnString()
{
	string str;
	getline(cin, str);
	return str;
}

//判斷輸入的計算式括号是否合法
bool Bracket_isMatched(string str)
{
	LinkStack<char> S;
	for (int i = 0; i != str.length(); ++i)
	{
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			S.Push(str[i]);
		else if (str[i] == ')' || str[i] == ']' || str[i] == '}')
		{
			if (S.isEmpty())
				return false;
			else
			{
				char temp = S.GetTop();
				S.Pop();
				if (temp == '(' && str[i] != ')' || temp == '[' && str[i] != ']'
					|| temp == '{' && str[i] != '}')
					return false;
			}
		}
	}
	return S.isEmpty();
}
           

 Calculate.h 

#pragma once
#include <iostream>
#include"MyStack.h"
using namespace std;

//用棧計算中綴表達式
int Calculate();
//運算
int opera(int left, int right, char c);
//判斷運算符優先級,判斷c1優先級是不是小于或等于c2
bool Priority(char c1, char c2);
//彈出并擷取一個運算符，彈出并擷取操作數，計算之後将結果壓入操作數棧
void GetCalculate(LinkStack<char>& S_char, LinkStack<int>& S_int);
           

 Calculate.cpp

#include<iostream>
#include"Calculate.h"
#include"BracketMatch.h"
#include"MyStack.h"

using namespace std;

/*
	1.用棧實作中綴表達式轉字尾表達式
		初始化一個棧，用于儲存暫時還不能确定運算順序的運算符
		從左到右處理各個元素，直到末尾。可能遇到三種情況：
			①遇到操作數。直接加入字尾表達式；
			②遇到界限符。遇到"("直接入棧；遇到")"則一次彈出棧内運算符并加入
			字尾表達式，直到彈出"("為止。注意"("不加入字尾表達式
			③遇到運算符。依次彈出棧中優先級高于或等于目前運算符的所有運算符，
			并加入字尾表達式
*/
/*
	2.用棧實作字尾表達式計算
		1.從左往右掃描下一個元素，直到處理完所有元素
		2.若掃描到操作數則壓入棧，并回到1.；否則執行3.
		3.若掃描到運算符。則彈出棧頂的連個元素，執行相應的運算，運算結果壓回
		棧頂，回到1.
*/

/*
	3.用棧實作中綴表達式的計算
		初始化兩個棧，操作數棧和運算符棧
		若掃描到操作數，則壓入操作數棧
		若掃描到運算符或界限符，則按照“中綴轉字尾相同的邏輯壓入運算符棧（
		期間也會彈出運算符，每當彈出一個運算符時，就需要彈出兩個操作數棧的
		棧頂元素并執行相應運算，運算結果再壓回操作數棧）”
*/

//運算
int opera(int left,int right,char c)
{
	if (c == '+')
		return left + right;
	else if(c=='-')
		return left - right;
	else if(c=='*')
		return left * right;
	else if(c=='/')
		return left / right;
}

//彈出并擷取一個運算符，彈出并擷取操作數，計算之後将結果壓入操作數棧
void GetCalculate(LinkStack<char>& S_char, LinkStack<int>& S_int)
{
	char c = S_char.GetTop();
		S_char.Pop();
		int left, right;
		//擷取操作數
		right = S_int.GetTop();
		S_int.Pop();
		left = S_int.GetTop();
		S_int.Pop();
		//進行計算,并壓入操作數棧
		S_int.Push(opera(left, right, c));
}

//判斷運算符優先級,判斷c1優先級是不是小于或等于c2
bool Priority(char c1, char c2)
{
		if ((c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-'))
			return false;
		else
			return true;
}

//用棧計算中綴表達式
int Calculate()
{
	string str = EnString();
	if (Bracket_isMatched(str))
	{
		LinkStack<char> S_char;//運算符棧
		LinkStack<int> S_int;//操作數棧
		int num = 0;
		int flag = 0;
		for (int i = 0; i != str.length(); ++i)
		{
			if(str[i] >= '0' && str[i] <= '9')//若遇到數字則将字元轉換為數字
			{
				num = num * 10 + str[i] - '0';
				++flag;
				if (flag != 0 && i == str.length() - 1)
				{
					S_int.Push(num);//數字轉換結束後壓入操作數棧
					num = 0;//num清零
					flag = 0;
				}
			}
			else
			{
				if (flag != 0)//說明num被修改過
				{
					S_int.Push(num);//數字轉換結束後壓入操作數棧
					num = 0;//num清零
					flag = 0;
				}
				if (str[i] == '(')//遇到'('直接入運算符棧
					S_char.Push(str[i]);
				else if (str[i] == ')')
				{
					while (S_char.GetTop() != '(' )
					{
						GetCalculate(S_char, S_int);
					}
						S_char.Pop();
				}
				else if (str[i] == '+' || str[i] == '-' || str[i] == '*' ||
					str[i] == '/')
				{
						while (S_char.GetTop() != '('&& !S_char.isEmpty()
							&& Priority(str[i], S_char.GetTop()))
						{
								GetCalculate(S_char, S_int);
						}
						S_char.Push(str[i]);
				}
			}
		}
		while (!S_char.isEmpty())//判斷操作符棧是否空，不空則進行計算
		{
			GetCalculate(S_char, S_int);
		}
		return S_int.GetTop();
	}
	else
	{
		cout << "括号不比對" << endl;
		return -9999;
	}
}
           

 main.cpp

#include <iostream>
#include"MyStack.h"
#include"BracketMatch.h"
#include"Calculate.h"
using namespace std;

int main()
{
    cout << Calculate() << endl;
    return 0;
}