【描述】
堆疊可以應用于算術運算式求值。這里對算術運算式做如下簡化：運算子為+、-、*、/、%；運算元為單數字（0～9）非負整數。
例如：(2+5)*3-8/3
上述形式的算術運算式也稱中綴運算式，因為每個運算子出現在它的兩個運算元之間。編譯器在求算術運算式值時，往往將中綴運算式轉換為后綴運算式。后綴運算式也稱逆波蘭運算式，由波蘭數學家Jan Lukasiewicz發明，指運算子出現在運算元后面的不含括號的算術運算式。
中綴運算式：a+b*c，其后綴運算式為：a b c * +。因為*的優先級比+高，所以先計算b*c，即b c *；+的運算元是a和b c *，即a b c * +。
中綴運算式：(a+b)*c，其后綴運算式為：a b + c *。先計算圓括號中a+b，即a b +；*的運算元是a b +和c，即a b + c *。
中綴運算式：(a*b+c)/d+e，其后綴運算式為：a b * c + d / e +。先計算圓括號中a*b+c，即a b * c +；/的運算元是a b * c +和d，即a b * c + d /；+的運算元是a b * c + d /和e，即a b * c + d / e +。
后綴運算式求值使用一個存放運算元的堆疊。求值程序順序掃描后綴運算式，每次遇到運算元就將它入堆疊；遇到運算子時，就從堆疊中彈出兩個運算元進行計算，并將結果入堆疊。到掃描結束，留在堆疊頂的運算元就是所求算術運算式的值。
例如：
4 2 7 *+
如下圖一所示，順序讀取運算元4、2、7，并入堆疊。如下圖二所示，讀取運算子*，運算元7、2出堆疊，計算2*7，結果為14并入堆疊。如下圖三所示，讀取運算子+，運算元14、4出堆疊，計算4+14，結果為18并入堆疊。掃描后綴運算式后，堆疊中惟一元素即為最終結果。
請組合堆疊類Stack，宣告并實作一個PostfixEvaluation類，求后綴運算式的值。PostfixEvaluation類包括：
string型別的私有資料成員postfixExpression，存放后綴運算式。
Stack型別的私有資料成員operandStack，存放運算元（單數字非負整數）。
私有成員函式getOperands，連續從堆疊頂出堆疊兩個運算元。
私有成員函式calculate，求出堆疊的兩個運算元的計算結果，并將結果入堆疊。
私有成員函式isOperator，確定輸入的運算子是有效運算子（+、-、*、/、%）
有參建構式。新建一個后綴運算式物件。
訪問器函式getPostfixExpression，獲取后綴運算式。
更改器函式setPostfixExpression，設定新的后綴運算式。
成員函式evaluate，計算并回傳后綴運算式的值。
PostfixEvaluation類如下：
class PostfixEvaluation {
public:
PostfixEvaluation(const string&postfixExpression); // 建構式
stringgetPostfixExpression() const; // 獲取后綴運算式
void setPostfixExpression(const string&postfixExpression); // 設定后綴運算式
int evaluate(); // 計算并回傳后綴運算式值
private:
string postfixExpression; // 存放要計算的后綴運算式
Stack<int> operandStack; // 存放運算元
void getOperands(int &left, int&right); // 運算元出堆疊
int calculate(int left, int right, char op) const; // 求運算元運算值
bool isOperator(char ch) const; // 是否是運算子
};
【輸入】
輸入一個后綴運算式。
【輸出】
輸出后綴運算式的值。
【輸入示例1】
4 2 7 * +
【輸出示例1】
18
【輸入示例2】
8 4 0 % +
【輸出示例2】
Divisor cannot be zero!
【輸入示例3】
2 3 ^ 4 +
【輸出示例3】
Illegal input!
【輸入示例4】
4 2 / *
【輸出示例4】
Too many operators!
【輸入示例5】
1 2 3 +
【輸出示例5】
Too many operands!
#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;
template <typename T>
class Vector {
public:
Vector(int size); // 建構式
Vector(int size, const T& value); // 建構式
Vector(const Vector<T>& v); // 拷貝建構式
virtual ~Vector(); // 解構式
const Vector<T>& operator=(const Vector<T>& right); // 多載賦值運算子
T& operator[](int index); // 多載下標運算子
T operator[](int index) const; // 多載下標運算子
int getSize() const;
void resize(int size);
private:
T* pVector; // 指標，指向存放陣列元素的動態分配記憶體空間
int size; // 陣列長度
};
template <typename T>
Vector<T>::Vector(int size) {
if (size > 0)
this->size = size;
else
throw invalid_argument("陣列長度必須是正整數!");
pVector = new T[size];
}
template <typename T>
Vector<T>::Vector(int size, const T& value) {
if (size > 0)
this->size = size;
else
throw invalid_argument("陣列長度必須是正整數!");
pVector = new T[size];
for (int i = 0; i < size; ++i)
pVector[i] = value;
}
template <typename T>
Vector<T>::Vector(const Vector<T>& v) {
size = v.size;
pVector = new T[size];
for (int i = 0; i < size; ++i)
pVector[i] = v.pVector[i];
}
template <typename T>
Vector<T>::~Vector() {
delete[] pVector;
}
template <typename T>
const Vector<T>& Vector<T>::operator=(const Vector<T>& right) {
if (this != &right) {
if (size != right.size) {
delete[] pVector;
size = right.size;
pVector = new T[size];
}
for (int i = 0; i < size; ++i)
pVector[i] = right.pVector[i];
}
return *this;
}
template <typename T>
T& Vector<T>::operator[](int index) {
if (index < 0 || index > size - 1)
throw out_of_range("陣列下標超出允許范圍!");
return pVector[index];
}
template <typename T>
T Vector<T>::operator[](int index) const {
if (index < 0 || index > size - 1)
throw out_of_range("陣列下標超出允許范圍!");
return pVector[index];
}
template <typename T>
int Vector<T>::getSize() const {
return size;
}
template <typename T>
void Vector<T>::resize(int size) {
if (size > 0) {
if (this->size != size) {
T* old = pVector;
pVector = new T[size];
int newSize = (this->size > size) ? size : this->size;
for (int i = 0; i < newSize; ++i)
pVector[i] = old[i];
this->size = size;
delete[] old;
}
}
else
throw invalid_argument("陣列長度必須是正整數!");
}
template <typename T>
class Stack {
public:
Stack(int size = 16); // 建構式
Stack(const Stack<T>& v); // 拷貝建構式
void clear(); // 將堆疊設定為空堆疊
bool isEmpty() const; // 判斷堆疊是否為空
void push(T value); // 入堆疊
T pop(); // 出堆疊
T peek() const; // 獲取堆疊頂元素
private:
Vector<T> data; // 存放堆疊元素
int top; // 記錄堆疊頂位置
};
template <typename T>
Stack<T>::Stack(int size) :data(size) {
clear();
}
template <typename T>
Stack<T>::Stack(const Stack<T>& v)
: data(v.data), top(v.top) { }
template <typename T>
void Stack<T>::clear() {
top = 0;
}
template <typename T>
bool Stack<T>::isEmpty() const {
return top == 0;
}
template <typename T>
void Stack<T>::push(T value) {
if (top >= data.getSize())
data.resize(2 * data.getSize());
data[top++] = value;
}
template <typename T>
T Stack<T>::pop() {
return data[--top];
}
template <typename T>
T Stack<T>::peek() const {
return data[top - 1];
}
/* 請在此處撰寫PostfixEvaluation類 */
int main() {
string expression;
getline(cin, expression);
PostfixEvaluation exp(expression);
try {
cout << exp.evaluate() << endl;
}
catch (runtime_error & ex) {
cout << ex.what() << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/55031.html
標籤：新手樂園
上一篇：go 中recover捕獲例外