本文主要是介绍【数据结构与算法 | 基础篇】栈：中缀表达式转变为后缀表达式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 前言
假设我们已经知道中缀表达式和后缀表达式的概念. 我们可以用符号栈来实现中缀表达式向后缀表达式的转变.
2. 符号栈实现中缀表达式转变为后缀表达式
(1). 思路
我们设计了可变字符串与符号栈. 如果传入的字符串的字符是数字字符，则直接将该字符append到stringbuilder中. 如果该字符是符号字符，首先先判断符号栈是否为空，如果为空，则直接将该字符压栈，如果不为空，则需要将该字符与栈顶字符进行优先级比较.如果栈顶元素的优先级＞该字符，毫无疑问，直接将栈顶元素弹栈.如果栈顶元素与该元素优先级相等，由于计算的顺序是从左到右，所以仍然需要将栈顶元素弹栈. 弹栈过程结束以后，需要将该字符压栈.
(2). 解
//将中缀表达式转变为后缀表达式
//目前只讨论没有小括号的情况
public class postfixexpr {public StringBuilder postfix(String s) throws Exception {//符号栈Deque<Character> deque = new LinkedList<>();StringBuilder str = new StringBuilder();int i = 0;for (; i < s.length(); i++) {char c = s.charAt(i);//如果该字符是数字字符, 那么将该字符加入到可变字符串if(isNumber(c)) {str.append(c);} else {//如果栈空, 则直接将该符号压栈//如果不为空, 则将栈顶元素与该字符作比较//if栈顶元素优先级大于等于该元素, 全部弹栈if(deque.isEmpty()) {deque.push(c);} else {while(!deque.isEmpty() && priority(deque.peek()) >= priority(c)){str.append(deque.pop());}deque.push(c);}}}while(!deque.isEmpty()) {str.append(deque.pop());}return str;}//设计判断符号优先级的函数private int priority(char c) throws Exception {if (c == '+' || c == '-') {return 1;} else if (c == '*' || c == '/') {return 2;} else {throw new Exception();}}private boolean isNumber(char c) {if (c == '+' || c == '-' || c == '*' || c == '/') {return false;}return true;}
}
这篇关于【数据结构与算法 | 基础篇】栈：中缀表达式转变为后缀表达式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
