逆波蘭式的解釋
逆波蘭記法中,操作符置于操作數的後面。例如表達“三加四”時,寫作“3 4 +”,而不是“3 + 4”。如果有多個操作符,操作符置于第二個操作數的後面,是以正常中綴記法的“3- 4 + 5”在逆波蘭記法中寫作“3 4- 5 +”:先3減去4,再加上5。使用逆波蘭記法的一個好處是不需要使用括号。例如中綴記法中“3 - 4 * 5”與“(3 - 4)*5”不相同,但字尾記法中前者寫做“3 4 5 * -”,無歧義地表示“3 (4 5 *) −”;後者寫做“3 4 - 5 *”。
逆波蘭表達式的解釋器一般是基于堆棧的。解釋過程一般是:操作數入棧;遇到操作符時,操作數出棧,求值,将結果入棧;當一遍後,棧頂就是表達式的值。是以逆波蘭表達式的求值使用堆棧結構很容易實作,和能很快求值。
注意:逆波蘭記法并不是簡單的波蘭表達式的反轉。因為對于不滿足交換律的操作符,它的操作數寫法仍然是正常順序,如,波蘭記法“/ 6 3”的逆波蘭記法是“6 3 /”而不是“3 6 /”;數字的數位寫法也是正常順序。
轉自;http://blog.csdn.net/jiangwlee/article/details/7182537
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
class Solution {
private:
stack<int> IntStack;
public:
int evalRPN(vector<string> &tokens);
bool IsNum(char token);
};
bool Solution::IsNum(char token)
{
if('+'==token||'-'==token||'/'==token||'*'==token)
return false;
else
return true;
}
int Solution::evalRPN(vector<string> &tokens)
{
int temp1,temp2;
for(int i=0;i<tokens.size();i++)
{
if("+"!=tokens[i]&&"-"!=tokens[i]&&"/"!=tokens[i]&&"*"!=tokens[i])
IntStack.push(atoi(tokens[i].c_str()));
else
{
temp1 = IntStack.top();
IntStack.pop();
temp2 = IntStack.top();
IntStack.pop();
if("+" == tokens[i])
IntStack.push(temp1+temp2);
if("-" == tokens[i])
IntStack.push(temp2-temp1);
if("*" == tokens[i])
IntStack.push(temp2*temp1);
if("/" == tokens[i])
IntStack.push(temp2/temp1);
}
}
return IntStack.top();
}
int main()
{
string str[] = {"4", "13", "5", "/", "+"};
vector<string> tokens(str,str+sizeof(str)/sizeof(str[0]));
Solution *solution = new Solution;
cout << solution->evalRPN(tokens)<< endl;
return 0;
}