Reverse Polish notation(逆波兰式)

介绍

逆波兰式（也叫后缀表达式）是一种将算数表达式的运算符写在操作数后面的表示方法。例如，在传统的波兰式（中缀表达式）中，表达式 (1+2)*(5+4) 在逆波兰式中可以表示为 1 2 + 5 4 + * 。逆波兰式的优点之一是它是无括号。

逆波兰式的计算

新建一个表达式,如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

代码如下：

#include <iostream> #include <stack> #include <cstdlib> #include <cstdio> using namespace std; int main() { stack<int> stack; string input; while(cin >> input) { if(input == "+") { int post = stack.top(); stack.pop(); int pre = stack.top(); stack.pop(); stack.push(pre + post); } else if(input == "-") { int post = stack.top(); stack.pop(); int pre = stack.top(); stack.pop(); stack.push(pre - post); } else if(input == "*") { int post = stack.top(); stack.pop(); int pre = stack.top(); stack.pop(); stack.push(pre * post); } else if(input == "/") { int post = stack.top(); stack.pop(); int pre = stack.top(); stack.pop(); stack.push(pre / post); } else stack.push(atoi(input.c_str())); } cout << stack.top() << endl; return 0; }

中缀表达式（Infix）转换为后缀表达式( Postfix )

中缀式是人们最常使用的表达式了，但怎么把它转换为电脑擅长的后缀式呢？

首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级最低的运算符‘#’。注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非‘#’不可。

不多赘述了，直接上代码：

#include <cstdio> #include <cstring> #include <cctype> //char stack char stack[25]; int top = -1; void push(char item) { stack[++top] = item; } char pop() { return stack[top--]; } //返回操作符的优先级 int precedence(char symbol) { switch(symbol) { case '+': case '-': return 2; break; case '*': case '/': return 3; break; case '^': return 4; break; case '(': case ')': case '#': return 1; break; } } //检查符号是否是操作符 int isOperator(char symbol) { switch(symbol) { case '+': case '-': case '*': case '/': case '^': case '(': case ')': return 1; break; default: return 0; } } //将中缀表达式转换为后缀 void convert(char infix[],char postfix[]) { int i,symbol,j = 0; stack[++top] = '#'; for(i = 0;i<strlen(infix);i++) { symbol = infix[i]; if(isOperator(symbol) == 0) //若取出的字符是操作数 { postfix[j] = symbol; //分析出完整的运算数，该操作数直接送入栈2 j++; } else { if(symbol == '(') //若取出的字符是'('，则直接送入S1栈顶。 { push(symbol); } else { if(symbol == ')') //若取出的字符是')'，则将距离S1栈栈顶最近的'('之间的运算符，逐个出栈，依次送入S2栈，再抛弃'('。 { while(stack[top] != '(') { postfix[j] = pop(); j++; } pop(); //pop out (. } else { if(precedence(symbol)>precedence(stack[top])) //判定优先级 { push(symbol); //大于S1栈栈顶运算符优先级，则将该运算符进S1栈 } else //否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于该运算符优先级，最后将该运算符送入S1栈 { while(precedence(symbol)<=precedence(stack[top])) { postfix[j] = pop(); j++; } push(symbol); } } } } } while(stack[top] != '#') //若取出的字符是“#”，则将S1栈内所有运算符，逐个出栈，依次送入S2栈。 { postfix[j] = pop(); j++; } postfix[j]='\0'; //null terminate string. } int main() { char infix[25] = "1*(2+3)",postfix[25]; convert(infix,postfix); printf("Infix expression is: %s\n" , infix); printf("Postfix expression is: %s\n" , postfix); return 0; }