逆波兰式的产生及计算(C++版)---编译原理

逆波兰式的产生及计算(C++版及Java版本)—编译原理,数据结构

在现实生活中大家对于计算使用都是中缀表达式(nifix expression),如但是在计算机中表达式常常是以后缀表达式(postfix expression),又称逆波兰表达式(reverse Polish notation, RPN ).

例如:中缀表达式 1+((2+3)*4)-5

​ 逆波兰表达式: 1 2 3 + 4 * + 5

1.逆波兰表达式的转换

1.1逆波兰表达式的转换概念图

1.2逆波兰表达式转换规则

​ 操作符优先级

运算符优先级+ -1* /2(3(入栈后变为最低) 从左到右依次扫描中缀表达式如果输入带当前元素为 数字 ,直接输出到输出带中.如果输入带当前元素为 运算符 如果当前操作符堆栈为 空, 不管是什么运算符都直接push压入堆栈中.如果当前输入带操作符为 ‘)’,一直pop弹出栈顶元素到输出带中,直到遇到’(’ tip: 括号不输出如果当前输入带操作符不为’)’ 如果操作符堆栈中栈顶运算符的优先级 大于等于 输入带当前运算符优先级,则将操作符堆栈栈顶pop弹出,并输出到输出带中,直到栈顶优先级 小于 当前优先级如果操作符堆栈中栈顶运算符的优先级 小于 输入带当前运算符优先级,则将当前运算符push压栈 当输入带扫描完成,将操作符堆栈中剩余运算符pop弹出到输出带中

2.逆波兰表达式的计算

2.1逆波兰表达式的计算模型

2.2逆波兰表达式的计算规则

例如对于 1 2 3 + 4 * + 5

对输入带从左到右依次扫描如果 输入带当前元素为数字,将其push压入运算数堆栈如果 输入带当前元素为运算符,取出运算数堆栈栈顶的两个元素,第一个栈顶元素为右运算数,第二个栈顶元素为左运算数,再将运算结果压入栈顶扫描结束后,运算数堆栈剩余的一个元素就是结果

3.逆波兰表达式转换过程表

​ 例如 1+((2+3)4)-5

4.逆波兰表达式计算过程表

​ 例:1 2 3 + 4 * + 5 -

代码(cpp版)

#include <iostream> #include <stack> #include <string> #include <map> #include <queue> #include <algorithm> using namespace std; bool isDigit(char ch); void getPostfixNotation(); void initializeOperatorPriority(); int dealWithDigit(int i); void dealWithOperator(int i); string transCharToString(char ch); void showPostfixNotation(); bool isOperator(string str); int calculate(char ch); int stackCalculate(); queue<string> postfixNotation; stack<char> operators; map<char, int> operatorPriority; stack<int> calculateStack; string expression; int main() { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); cin >> expression; initializeOperatorPriority(); getPostfixNotation(); showPostfixNotation(); stackCalculate(); cout << calculateStack.top() << endl; return 0; } void initializeOperatorPriority() { operatorPriority['+'] = 1; operatorPriority['-'] = 1; operatorPriority['*'] = 2; operatorPriority['/'] = 2; operatorPriority['('] = 3; } void getPostfixNotation() { for (int i = 0; i < expression.length();) { if (isDigit(expression[i])) { i = dealWithDigit(i); } else { dealWithOperator(i); i++; } } postfixNotation.push(transCharToString(operators.top())); operators.pop(); } bool isDigit(char ch) { bool flag = false; if (ch >= '0' and ch <= '9') { flag = true; } return flag; } int dealWithDigit(int i) { string number; number += expression[i++]; while (isDigit(expression[i])) { number += expression[i++]; } postfixNotation.push(number); return i; } void dealWithOperator(int i) { if (operators.empty()) { operators.push(expression[i]); } else { if (expression[i] != ')') { while (!operators.empty() and operatorPriority[operators.top()] >= operatorPriority[expression[i]] and operators.top() != '(') { postfixNotation.push(transCharToString(operators.top())); operators.pop(); } operators.push(expression[i]); } else { while (operators.top() != '(') { postfixNotation.push(transCharToString(operators.top())); operators.pop(); } operators.pop(); } } } string transCharToString(char ch) { string temp = " "; temp[0] = ch; return temp; } void showPostfixNotation() { int postfixNotation_size = postfixNotation.size(); for (int i = 0; i < postfixNotation_size; i++) { cout << postfixNotation.front() << " "; postfixNotation.push(postfixNotation.front()); postfixNotation.pop(); } cout << endl; } int stackCalculate() { while (!postfixNotation.empty()) { if (isOperator(postfixNotation.front())) { int result = calculate(postfixNotation.front()[0]); calculateStack.push(result); } else { int number = atoi(postfixNotation.front().c_str()); calculateStack.push(number); } postfixNotation.pop(); } return 0; } int calculate(char ch) { int result; int right = calculateStack.top(); calculateStack.pop(); int left = calculateStack.top(); calculateStack.pop(); switch (ch) { case '+': result = left + right; break; case '-': result = left - right; break; case '*': result = left * right; break; case '/': result = left / right; break; } return result; } bool isOperator(string str)//return '0' means its not operator { bool flag = true; if (str[0] >= '0' and str[0] <= '9') { flag = false; } return flag; } //21+((42-2)*15+6)-18 //1 + ((2 + 3) * 4) - 5

Java版本

public class ReversePolishNotation { // integer bigger means higher priority private static Map<String, Integer> priority = new HashMap<>(); //set the base priority static { priority.put("(", 4); priority.put("*", 3); priority.put("/", 3); priority.put("-", 2); priority.put("+", 2); } public static Integer reversePolish(String infixNotation) { List<String> newInfixNotation = getNewInfixNotation(infixNotation); List<String> prefixNotation = transFromInfixToPrefix(newInfixNotation); Integer result = calculate(prefixNotation); return result; } //transform (string)infixNotation to (list<string>)infixNotation public static List<String> getNewInfixNotation(String infixNotation) { List<String> newInfixNotation = new ArrayList<>(); for (int cnt = 0; cnt < infixNotation.length(); ++cnt) { char nowChar = infixNotation.charAt(cnt); //find the continuous digits and combine if(Character.isDigit(nowChar)) { StringBuffer temp = new StringBuffer(); while (cnt < infixNotation.length() && Character.isDigit(infixNotation.charAt(cnt))) { temp.append(infixNotation.charAt(cnt)); ++cnt; } --cnt; newInfixNotation.add(temp.toString()); } //else if nowChar is operator else if(nowChar != ' ') { newInfixNotation.add(String.valueOf(nowChar)); } } return newInfixNotation; } //transform infixNotation to prefixNotation public static List<String> transFromInfixToPrefix(List<String> infixNotation) { List<String> result = new ArrayList<>(); Stack<String> operator = new Stack<>(); for (String s : infixNotation) { //if its not digit if(!Character.isDigit(s.charAt(0))) { if(!operator.isEmpty()) { if(s.equals(")")) { while (!operator.isEmpty() && !operator.peek().equals("(")) { result.add(operator.pop()); } operator.pop(); } else { while (!operator.isEmpty() && priority.get(operator.peek()) >= priority.get(s) && !operator.peek().equals("(")) { result.add(operator.pop()); } operator.push(s); } } else { operator.push(s); } } // if its digit else {result.add(s);} } while (!operator.isEmpty()) {result.add(operator.pop());} return result; } // calculate the result by prefixNotation public static Integer calculate(List<String> prefixNotation) { Stack<Integer> calculateStack = new Stack<>(); for (String str : prefixNotation) { if(Character.isDigit(str.charAt(0))) { calculateStack.push(Integer.parseInt(str)); } else { Integer after = calculateStack.pop(); Integer before = calculateStack.pop(); Integer result = 0; switch (str) { case "+": result = before + after; break; case "-": result = before - after; break; case "*": result = before * after; break; case "/": result = before / after; break; } calculateStack.push(result); } } return calculateStack.pop(); } public static void main(String[] args) { String temp="1+((2+3)*4)-5"; System.out.println(reversePolish(temp));//结果是16正确 } }