逆波兰式
定义
一个表达式E的后缀形式可以如下定义：
（1）如果E是一个变量或常量，则E的后缀式是E本身。
（2）如果E是E1 op E2形式的表达式，这里op是如何二元操作符，则E的后缀式为E1’E2’ op，这里E1’和E2’分别为E1和E2的后缀式。
（3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
作用:
实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式 转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
算法实现
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：
（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
（5）重复上面的1~4步，直至处理完所有的输入字符
（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。
完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！
class TransformReversePolishNotation {
private:
stack<char> temp;
stack<char> rpn;
unordered_map<char, int> dict;
void init() {
//初始化字典
dict['#'] = -1;
dict['+'] = 1;
dict['-'] = 1;
dict['*'] = 2;
dict['/'] = 2;
dict['('] = 0;
dict[')'] = 0;
}
public:
stack<char> pn2rpn(string s) {
stack<char> result;
init();
temp.push('#');
for (int i = 0; i < s.size(); ++i) {
if (dict.count(s[i]) == 0) {//如果这个字符不存在
rpn.push(s[i]);//将操作数入栈
} else if (s[i] == '(') {//直接进temp中
temp.push(s[i]);
}else if (s[i] == ')') {//将(间的元素放入pn,删除(
while(temp.top()!='(') {//当temp的栈顶不为(且,当前运算符的优先级小于或等于栈顶
rpn.push(temp.top());//将temp栈顶元素放进pn中
temp.pop();//将栈顶元素出栈
}
temp.pop();//删除'('
} else {//各种运算符
for (;dict[s[i]] <= dict[temp.top()];temp.pop()) {//当temp的栈顶不为(且,当前运算符的优先级小于或等于栈顶
rpn.push(temp.top());//将temp栈顶元素放进pn中
// temp.pop();//将栈顶元素出栈
}
if(dict[s[i]] > dict[temp.top()])
temp.push(s[i]);
}
}
for(;dict[temp.top()]>0;temp.pop())
rpn.push(temp.top());//将temp栈顶元素放进pn中
//遍历并逆序
for (; rpn.size() > 0; rpn.pop())
result.push(rpn.top());
return result;
}
};
计算方法
新建一个表达式,如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
举例
下面以(a+b)c为例子进行说明： (a+b)c的逆波兰式为ab+c，假设计算机把ab+c按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理，那么ab+c的执行结果如下： 1）a入栈（0位置） 2）b入栈（1位置） 3）遇到运算符“+”，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置） 4）c入栈（1位置） 5）遇到运算符“”，将d和c出栈，执行d*c的操作，得到结果e，再将e入栈（0位置） 经过以上运算，计算机就可以得到(a+b)*c的运算结果e了。 逆波兰式除了可以实现上述类型的运算，它还可以派生出许多新的算法，数据结构，这就需要灵活运用了。逆波兰式只是一种序列体现形式。
简单实现:10以内的式子
class TransformReversePolishNotation {
private:
stack<char> temp;
stack<char> rpn;
unordered_map<char, int> dict;
void init() {
//初始化字典
dict['#'] = -1;
dict['+'] = 1;
dict['-'] = 1;
dict['*'] = 2;
dict['/'] = 2;
dict['('] = 0;
dict[')'] = 0;
}
int computeRPN(stack<char> rpn) {
init();
vector<int> count;
while (rpn.size() > 0) {
for (; rpn.size() > 0 && dict.find(rpn.top()) == dict.end(); rpn.pop()) {//如果栈顶是操作数
int num = (int) rpn.top() - 48;
// int number = atoi(num);//转换字符串的,用来处理123+1213等
count.push_back(num);
}
switch (rpn.top()) {
case '+':
count[count.size() - 2] += count[count.size() - 1];
count.pop_back();
rpn.pop();
break;
case '-':
count[count.size() - 2] -= count[count.size() - 1];
count.pop_back();
rpn.pop();
break;
case '*':
count[count.size() - 2] *= count[count.size() - 1];
count.pop_back();
rpn.pop();
break;
case '/':
count[count.size() - 2] =
count[count.size() - 1] != 0 ? count[count.size() - 2] * count[count.size() - 1] : count[
count.size() - 2];
count.pop_back();
rpn.pop();
break;
default:
cout<<"不支持的运算类型";
}
}
return count[0];
}
};
leetcode 150:逆波兰式计算: 题解:
class Solution {
public:
int evalRPN(vector<string>& tokens) {
if (tokens.empty()) return 0;
stack<long long int> st;
for (auto token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = st.top();
st.pop();
int a = st.top();
st.pop();
if (token == "+") {
st.push(a+b);
} else if (token == "-") {
st.push(a-b);
} else if (token == "*") {
st.push(a*b);
} else if (token == "/") {
st.push(a/b);
}
} else {
st.push(stoi(token));
}
}
return (int)st.top();
}
};
Comments