逆波蘭表達式的實現

  一般情況下表達式是由操作數和運算符組成，例如算數表達式中通常將運算符放在兩個操作數中間，譬如a+b的形式，這種形式稱為中綴表達式，那么問題來了，是否有后綴表達，前綴表達式呢？？？

對，沒錯，這些后綴表達，前綴表達式都是由波蘭數學家Jan Lukasiewicz提出來的

把運算符寫在操作數之前，稱為波蘭表達式(Polish Expression)或前綴表達式(Prefix Expression)，如+AB；

把運算符寫在操作數之后，稱為逆波蘭表達式(Reverse Polish Expression)或后綴表達式(Suffix Expression)，如AB+；

    假如我們有一個表達式，應該如何求它的值呢？在這里棧就派上用場了，由于操作數在操作符前邊，所以按順序遍歷這個表達式，遇到操作數的時候就進棧，遇到操作符的時候就讓離操作符最近的兩個操作數出棧，并參加運算，然后將運算結果壓入棧中。過程如下圖所示：

要編寫逆波蘭表達式求解函數，就要將一個逆波蘭式當做一個數組去處理，而且這個數組應該是一個結構體數組，每個數組元素包含兩個內容，一個是數組元素的類型（操作數類型還是操作符類型），一個是這個類型對應的值。

 今天就暫且實現一下后綴表達式吧，在這里運用枚舉，能夠更清晰的表達哦

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<stack>

#include<assert.h>

using namespace std;

enum Type

{

OP_NUM,

OP_SYMBOL,

};

enum SYMBOL

{

ADD,

SUB,

MUL,

DIV,

};

//定義一個結構體數組包括數組的類型和數組的值

struct Cell

{

Type _type;

int _value;

};

//逆波蘭表達式計算函數

int CountRNP(Cell a[],size_t size)

{

stack <int> s;

//若函數參數一定不能為空的條件下必須用斷言

assert(a);

for(size_t i=0;i<size;i++)

{//數組里邊的元素若為數值，則直接壓入棧中

if(a[i]._type==OP_NUM)

{

s.push(a[i]._value);

}

//若數組里邊的元素不是值，而是運算符，則將離運算符最近的兩個元素出棧，進行運算

else

{

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 a[]={{OP_NUM, 12},{OP_NUM, 3},{OP_NUM, 4},

         {OP_SYMBOL,ADD},{OP_SYMBOL,MUL},

 {OP_NUM, 6},{OP_SYMBOL,SUB},{OP_NUM, 8},{OP_NUM, 2},

         {OP_SYMBOL,DIV},{OP_SYMBOL,ADD}};

size_t size =sizeof(a)/sizeof(Cell);

cout<<CountRNP(a, size)<<endl;

system("pause");

return 0;

}

運行結果：