从上树的根(root)节点 + 开始进行 LVR 走访的话,一开始会先进入根节点 + 的左边子节点 a (L+)。节点 a 没有左边子节点能进入(La 无法运行),直接开始访问节点 a (Va),然后节点 a 也没有右边子节点能进入(Ra 无法运行)。此时根节点 + 的左边子节点 a 就看完了,开始访问根节点 + (V+),然后进入右边的子节点 * (R+),节点 * 有左边子节点 b 能进入(L*)。节点 b 没有左边子节点能进入(Lb 无法运行),直接开始访问节点 b (Vb),然后节点 b 也没有右边子节点能进入(Rb 无法运行)。此时节点 * 的左边子节点 b 就看完了,开始访问节点 * (V*),然后进入右边的子节点 c (R*)。节点 c 没有左边子节点能进入(Lc 无法运行),直接开始访问节点 c (Vc),然后节点 c 也没有右边子节点能进入(Rc 无法运行)。此时 * 的右边子节点 c 就看完了,也就是说根节点 + 的右边子节点 * 也看完了。走访结束。
按照访问过的节点顺序,我们可以得到 a + (b * c) 这样的中序式。VLR 和 LRV 走访方式也是依此类推,本质上它们都是属于深度优先搜索。
参考以下代码来理解 preorder、inorder 和 postorder 的差别:
use std::cell::RefCell;
use std::rc::Rc;
#[derive(Debug)]
pub struct Node {
pub value: &'static str,
pub left_child: Option<Rc<RefCell<Node>>>,
pub right_child: Option<Rc<RefCell<Node>>>,
}
impl Node {
pub fn new(value: &'static str) -> Rc<RefCell<Node>> {
Rc::new(RefCell::new(Node {
value,
left_child: None,
right_child: None,
}))
}
pub fn rc_equal(a: &Rc<RefCell<Node>>, b: &Rc<RefCell<Node>>) -> bool {
let ref_a = a.borrow();
let ref_b = b.borrow();
&*ref_a as *const Node == &*ref_b as *const Node
}
pub fn set_children(
node: Rc<RefCell<Node>>,
children: Option<(Rc<RefCell<Node>>, Rc<RefCell<Node>>)>,
) {
let mut ref_node = node.borrow_mut();
match children {
Some((left_child, right_child)) => {
ref_node.left_child = Some(left_child);
ref_node.right_child = Some(right_child);
}
None => {
ref_node.left_child = None;
ref_node.right_child = None;
}
}
}
pub fn get_left_child(node: Rc<RefCell<Node>>) -> Option<Rc<RefCell<Node>>> {
node.borrow().left_child.as_ref().cloned()
}
pub fn get_right_child(node: Rc<RefCell<Node>>) -> Option<Rc<RefCell<Node>>> {
node.borrow().right_child.as_ref().cloned()
}
pub fn get_children(node: Rc<RefCell<Node>>) -> Option<(Rc<RefCell<Node>>, Rc<RefCell<Node>>)> {
let ref_node = node.borrow();
match &ref_node.left_child {
Some(left_child) => {
Some((left_child.clone(), ref_node.right_child.as_ref().unwrap().clone()))
}
None => None,
}
}
}
pub fn preorder(node: Option<Rc<RefCell<Node>>>) {
if let Some(node) = node {
print!("{} ", node.borrow().value); // V
preorder(Node::get_left_child(node.clone())); // L
preorder(Node::get_right_child(node)); // R
}
}
pub fn inorder(node: Option<Rc<RefCell<Node>>>) {
if let Some(node) = node {
inorder(Node::get_left_child(node.clone())); // L
print!("{} ", node.borrow().value); // V
inorder(Node::get_right_child(node)); // R
}
}
pub fn postorder(node: Option<Rc<RefCell<Node>>>) {
if let Some(node) = node {
postorder(Node::get_left_child(node.clone())); // L
postorder(Node::get_right_child(node.clone())); // R
print!("{} ", node.borrow().value); // V
}
}
pub fn preorder_iteratively(node: Rc<RefCell<Node>>) {
let mut stack = Vec::new();
stack.push(node);
while let Some(node) = stack.pop() {
print!("{} ", node.borrow().value);
if let Some((left_child, right_child)) = Node::get_children(node) {
stack.push(right_child);
stack.push(left_child);
}
}
}
pub fn inorder_iteratively(node: Rc<RefCell<Node>>) {
let mut stack = Vec::new();
let mut n = Some(node);
loop {
while let Some(node) = n.as_ref() {
stack.push(node.clone());
n = Node::get_left_child(node.clone());
}
if let Some(node) = stack.pop() {
print!("{} ", node.borrow().value);
n = Node::get_right_child(node);
} else {
break;
}
}
}
pub fn postorder_iteratively(node: Rc<RefCell<Node>>) {
let mut stack_1 = Vec::new();
let mut stack_2 = Vec::new();
stack_1.push(node);
while let Some(node) = stack_1.pop() {
if let Some((left_child, right_child)) = Node::get_children(node.clone()) {
stack_1.push(left_child);
stack_1.push(right_child);
}
stack_2.push(node);
}
while let Some(node) = stack_2.pop() {
print!("{} ", node.borrow().value);
}
}
根据后序式的运算方式,我们可以创建出一个堆栈(Stack)空间,来保存(push)当从左往右看后序式时所遇到的操作数。如此一来,在遇到操作符的时候,只要 pop 出堆栈空间中(顶部)的两个操作数,就可以让它们做运算,并把运算结果再次 push 回堆栈空间中,接着再继续往右看后序式的操作符和操作数。当算式看完了,最后在堆栈空间中剩下的元素就是答案了!
于是我们可以撰写出以下程序:
pub fn evaluate_postfix(postfix: &[&str]) -> f64 {
let mut stack = vec![];
for &op in postfix {
match op {
"+" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a + b);
}
"-" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a - b);
}
"*" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a * b);
}
"/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a / b);
}
operand => {
stack.push(operand.parse().unwrap());
}
}
}
stack.pop().unwrap()
}
public static double evaluatePostfix(final String[] postfix) {
final Stack<Double> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a + b);
break;
}
case "-": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a - b);
break;
}
case "*": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a * b);
break;
}
case "/": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a / b);
break;
}
default:
stack.push(Double.parseDouble(op));
}
}
return stack.pop();
}
function evaluatePostfix(postfix: string[]) {
const stack: number[] = [];
for (const op of postfix) {
switch (op) {
case "+": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a + b);
break;
}
case "-": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a - b);
break;
}
case "*": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a * b);
break;
}
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a / b);
break;
}
default:
stack.push(parseFloat(op));
}
}
return stack.pop();
}
type stack []float64
func (s stack) Push(v float64) stack {
return append(s, v)
}
func (s stack) Pop() (stack, float64) {
l := len(s)
return s[:l-1], s[l-1]
}
func EvaluatePostfix(postfix []string) float64 {
stack := make(stack, 0)
for _, op := range postfix {
switch op {
case "+":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a + b)
}
case "-":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a - b)
}
case "*":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a * b)
}
case "/":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a / b)
}
default:
operand, _ := strconv.ParseFloat(op, 64)
stack = stack.Push(operand)
}
}
_, operand := stack.Pop()
return operand
}
前序式的运算
前序式运算的程序实作方式,只需要把原本后序式运算的代码之算式的读取方向颠倒,再把从堆栈空间中 pop 出来的操作数反过来运算就好了。
于是我们可以撰写出以下程序:
pub fn evaluate_prefix(prefix: &[&str]) -> f64 {
let mut stack = vec![];
for &op in prefix.iter().rev() {
match op {
"+" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a + b);
}
"-" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a - b);
}
"*" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a * b);
}
"/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a / b);
}
operand => {
stack.push(operand.parse().unwrap());
}
}
}
stack.pop().unwrap()
}
public static double evaluatePrefix(final String[] prefix) {
final Stack<Double> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a + b);
break;
}
case "-": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a - b);
break;
}
case "*": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a * b);
break;
}
case "/": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a / b);
break;
}
default:
stack.push(Double.parseDouble(op));
}
}
return stack.pop();
}
function evaluatePrefix(prefix: string[]) {
const stack: number[] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a + b);
break;
}
case "-": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a - b);
break;
}
case "*": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a * b);
break;
}
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a / b);
break;
}
default:
stack.push(parseFloat(op));
}
}
return stack.pop();
}
type stack []float64
func (s stack) Push(v float64) stack {
return append(s, v)
}
func (s stack) Pop() (stack, float64) {
l := len(s)
return s[:l-1], s[l-1]
}
func EvaluatePrefix(prefix []string) float64 {
stack := make(stack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a + b)
}
case "-":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a - b)
}
case "*":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a * b)
}
case "/":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a / b)
}
default:
operand, _ := strconv.ParseFloat(op, 64)
stack = stack.Push(operand)
}
}
_, operand := stack.Pop()
return operand
}
后序式转前序式
如果不在乎输出的结果会把操作符和操作数混在一起成为一个字符串的话,后序式转前序式的程序实作只需要一个堆栈空间就可以完成了。作法有点类似后序式运算那样:看到操作数就把操作数 push 进堆栈空间中,看到操作符就从堆栈空间中 pop 出两个操作数,进行字符串的串接(串接成「操作符 操作数 操作数」)后,再把新字符串 push 进堆栈空间中。当算式看完了,最后在堆栈空间中剩下的元素就是原后序式被转换后的前序式了!
于是我们可以撰写出以下程序:
pub fn postfix_to_prefix_naive<'a>(postfix: &[&'a str]) -> Cow<'a, str> {
let mut stack = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(Cow::from(format!("{}{}{}", op, a, b)));
}
operand => {
stack.push(Cow::from(operand));
}
}
}
stack.pop().unwrap()
}
public static String postfixToPrefixNaive(final String[] postfix) {
final Stack<String> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String b = stack.pop();
final String a = stack.pop();
stack.push(op.concat(a).concat(b));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function postfixToPrefixNaive(postfix: string[]) {
const stack: string[] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(op + a + b);
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
type stack []string
func (s stack) Push(v string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PostfixToPrefixNaive(postfix []string) string {
stack := make(stack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(op + a + b)
}
default:
stack = stack.Push(op)
}
}
_, prefix := stack.Pop()
return prefix
}
pub fn postfix_to_prefix<'a>(postfix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
let mut c = Vec::with_capacity(1 + a.len() + b.len());
c.push(op);
c.extend_from_slice(&a);
c.extend_from_slice(&b);
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
public static String[] postfixToPrefix(final String[] postfix) {
final Stack<String[]> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] b = stack.pop();
final String[] a = stack.pop();
final String[] c = new String[1 + a.length + b.length];
c[0] = op;
System.arraycopy(a, 0, c, 1, a.length);
System.arraycopy(b, 0, c, 1 + a.length, b.length);
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
function postfixToPrefix(postfix: string[]) {
const stack: string[][] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
const c = [];
c.push(op);
c.push(...a);
c.push(...b);
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
type stack [][]string
func (s stack) Push(v []string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, []string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PostfixToPrefix(postfix []string) []string {
stack := make(stack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, b = stack.Pop()
stack, a = stack.Pop()
c := make([]string, 1+len(a)+len(b))
c[0] = op
copy(c[1:], a)
copy(c[(1+len(a)):], b)
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, prefix := stack.Pop()
return prefix
}
前序式转后序式
前序式转后序式的程序实作方式,只需要把原本后序式转前序式的代码之算式的读取方向颠倒,再把从堆栈空间中 pop 出来的操作数反过来进行字符串的串接(串接成「操作数 操作数 操作符」)。
于是我们可以撰写出以下程序:
pub fn prefix_to_postfix_naive(prefix: &[&str]) -> String {
let mut stack = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(format!("{}{}{}", a, b, op));
}
operand => {
stack.push(operand.to_string());
}
}
}
stack.pop().unwrap()
}
pub fn prefix_to_postfix<'a>(prefix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
let mut c = Vec::with_capacity(1 + a.len() + b.len());
c.extend_from_slice(&a);
c.extend_from_slice(&b);
c.push(op);
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
再优化一下 prefix_to_postfix 函数。
pub fn prefix_to_postfix<'a>(prefix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let mut a = stack.pop().unwrap();
let b = stack.pop().unwrap();
a.reserve(b.len() + 1);
a.extend_from_slice(&b);
a.push(op);
stack.push(a);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
public static String prefixToPostfixNaive(final String[] prefix) {
final Stack<String> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String a = stack.pop();
final String b = stack.pop();
stack.push(a.concat(b).concat(op));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
public static String[] prefixToPostfix(final String[] prefix) {
final Stack<String[]> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] a = stack.pop();
final String[] b = stack.pop();
final String[] c = new String[1 + a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
c[c.length - 1] = op;
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
function prefixToPostfixNaive(prefix: string[]) {
const stack: string[] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a + b + op);
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function prefixToPostfix(prefix: string[]) {
const stack: string[][] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
const c = [];
c.push(...a);
c.push(...b);
c.push(op);
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
type stringArrayStack [][]string
func (s stringArrayStack) Push(v []string) stringArrayStack {
return append(s, v)
}
func (s stringArrayStack) Pop() (stringArrayStack, []string) {
l := len(s)
return s[:l-1], s[l-1]
}
type stringStack []string
func (s stringStack) Push(v string) stringStack {
return append(s, v)
}
func (s stringStack) Pop() (stringStack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PrefixToPostfixNaive(prefix []string) string {
stack := make(stringStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a + b + op)
}
default:
stack = stack.Push(op)
}
}
_, postfix := stack.Pop()
return postfix
}
func PrefixToPostfix(prefix []string) []string {
stack := make(stringArrayStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, a = stack.Pop()
stack, b = stack.Pop()
c := make([]string, 1+len(a)+len(b))
copy(c, a)
copy(c[len(a):], b)
c[len(c)-1] = op
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, postfix := stack.Pop()
return postfix
}
pub fn postfix_to_infix_naive(postfix: &[&str]) -> String {
let mut stack = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(format!("({}{}{})", a, op, b));
}
operand => {
stack.push(operand.to_string());
}
}
}
stack.pop().unwrap()
}
pub fn postfix_to_infix<'a>(postfix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
let mut c = Vec::with_capacity(3 + a.len() + b.len());
c.push("(");
c.extend_from_slice(&a);
c.push(op);
c.extend_from_slice(&b);
c.push(")");
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
pub fn prefix_to_infix_naive(prefix: &[&str]) -> String {
let mut stack = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(format!("({}{}{})", a, op, b));
}
operand => {
stack.push(operand.to_string());
}
}
}
stack.pop().unwrap()
}
pub fn prefix_to_infix<'a>(prefix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
let mut c = Vec::with_capacity(3 + a.len() + b.len());
c.push("(");
c.extend_from_slice(&a);
c.push(op);
c.extend_from_slice(&b);
c.push(")");
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
public static String postfixToInfixNaive(final String[] postfix) {
final Stack<String> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String b = stack.pop();
final String a = stack.pop();
stack.push("(".concat(a).concat(op).concat(b).concat(")"));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
public static String[] postfixToInfix(final String[] postfix) {
final Stack<String[]> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] b = stack.pop();
final String[] a = stack.pop();
final String[] c = new String[3 + a.length + b.length];
c[0] = "(";
System.arraycopy(a, 0, c, 1, a.length);
c[1 + a.length] = op;
System.arraycopy(b, 0, c, 2 + a.length, b.length);
c[c.length - 1] = ")";
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
public static String prefixToInfixNaive(final String[] prefix) {
final Stack<String> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String a = stack.pop();
final String b = stack.pop();
stack.push("(".concat(a).concat(op).concat(b).concat(")"));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
public static String[] prefixToInfix(final String[] prefix) {
final Stack<String[]> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] a = stack.pop();
final String[] b = stack.pop();
final String[] c = new String[3 + a.length + b.length];
c[0] = "(";
System.arraycopy(a, 0, c, 1, a.length);
c[1 + a.length] = op;
System.arraycopy(b, 0, c, 2 + a.length, b.length);
c[c.length - 1] = ")";
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
function postfixToInfixNaive(postfix: string[]) {
const stack: string[] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push("(" + a + op + b + ")");
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function postfixToInfix(postfix: string[]) {
const stack: string[][] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
const c = [];
c.push("(");
c.push(...a);
c.push(op);
c.push(...b);
c.push(")");
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
function prefixToInfixNaive(prefix: string[]) {
const stack: string[] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push("(" + a + op + b + ")");
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function prefixToInfix(prefix: string[]) {
const stack: string[][] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
const c = [];
c.push("(");
c.push(...a);
c.push(op);
c.push(...b);
c.push(")");
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
type stringArrayStack [][]string
func (s stringArrayStack) Push(v []string) stringArrayStack {
return append(s, v)
}
func (s stringArrayStack) Pop() (stringArrayStack, []string) {
l := len(s)
return s[:l-1], s[l-1]
}
type stringStack []string
func (s stringStack) Push(v string) stringStack {
return append(s, v)
}
func (s stringStack) Pop() (stringStack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PostfixToInfixNaive(postfix []string) string {
stack := make(stringStack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push("(" + a + op + b + ")")
}
default:
stack = stack.Push(op)
}
}
_, infix := stack.Pop()
return infix
}
func PostfixToInfix(postfix []string) []string {
stack := make(stringArrayStack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, b = stack.Pop()
stack, a = stack.Pop()
c := make([]string, 3+len(a)+len(b))
c[0] = "("
copy(c[1:], a)
c[1+len(a)] = op
copy(c[(2+len(a)):], b)
c[len(c)-1] = ")"
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, infix := stack.Pop()
return infix
}
func PrefixToInfixNaive(prefix []string) string {
stack := make(stringStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push("(" + a + op + b + ")")
}
default:
stack = stack.Push(op)
}
}
_, infix := stack.Pop()
return infix
}
func PrefixToInfix(prefix []string) []string {
stack := make(stringArrayStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, a = stack.Pop()
stack, b = stack.Pop()
c := make([]string, 3+len(a)+len(b))
c[0] = "("
copy(c[1:], a)
c[1+len(a)] = op
copy(c[(2+len(a)):], b)
c[len(c)-1] = ")"
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, infix := stack.Pop()
return infix
}
fn get_priority(op: &str) -> Option<u8> {
match op {
"+" | "-" => Some(1),
"*" | "/" => Some(2),
_ => None,
}
}
pub fn infix_to_postfix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix {
if let Some(priority) = get_priority(op) {
if let Some(temp) = stack.last().copied() {
if priority <= get_priority(temp).unwrap() {
while let Some(temp) = stack.pop() {
out.push(temp);
}
}
}
stack.push(op);
} else {
out.push(op);
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out
}
public static int getPriority(final String op) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
return 0;
}
}
public static String[] infixToPostfix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (final String op : infix) {
final int priority = getPriority(op);
if (priority > 0) {
if (!stack.isEmpty()) {
final String temp = stack.peek();
if (priority <= getPriority(temp)) {
while (!stack.isEmpty()) {
out.add(stack.pop());
}
}
}
stack.push(op);
} else {
out.add(op);
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
return out.toArray(new String[out.size()]);
}
function getPriority(op: string) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
return 0;
}
}
function infixToPostfix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (const op of infix) {
const priority = getPriority(op);
if (priority > 0) {
if (stack.length > 0) {
const temp = stack[stack.length - 1];
if (priority <= getPriority(temp)) {
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
}
}
stack.push(op);
} else {
out.push(op);
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
return out;
}
type stack []string
func (s stack) Push(v string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func getPriority(op string) int {
switch op {
case "+", "-":
return 1
case "*", "/":
return 2
default:
return 0
}
}
func InfixToPostfix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for _, op := range infix {
priority := getPriority(op)
if priority > 0 {
if len(stack) > 0 {
temp := stack[len(stack)-1]
if priority <= getPriority(temp) {
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
}
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
return out
}
pub fn infix_to_postfix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix {
if let Some(priority) = get_priority(op) {
while let Some(temp) = stack.last().copied() {
if priority > get_priority(temp).unwrap() {
break;
}
out.push(temp);
unsafe {
stack.set_len(stack.len() - 1);
}
}
stack.push(op);
} else {
out.push(op);
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out
}
public static String[] infixToPostfix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (final String op : infix) {
final int priority = getPriority(op);
if (priority > 0) {
while (!stack.isEmpty()) {
final String temp = stack.peek();
if (priority > getPriority(temp)) {
break;
}
out.add(stack.pop());
}
stack.push(op);
} else {
out.add(op);
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
return out.toArray(new String[out.size()]);
}
function infixToPostfix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (const op of infix) {
const priority = getPriority(op);
if (priority > 0) {
while (stack.length > 0) {
const temp = stack[stack.length - 1];
if (priority > getPriority(temp)) {
break;
}
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
stack.push(op);
} else {
out.push(op);
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
return out;
}
func InfixToPostfix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for _, op := range infix {
priority := getPriority(op)
if priority > 0 {
for len(stack) > 0 {
temp := stack[len(stack)-1]
if priority > getPriority(temp) {
break
}
var e string
stack, e = stack.Pop()
out = append(out, e)
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
return out
}
#{{{
\begin{alignedat}{2}
a + b - c &{}\rightarrow{}&& a \text{ } b \text{ } + \text{ } c \text{ } - \\
a + ( b - c ) &{}\rightarrow{}&& a \text{ } b \text{ } c \text{ } - \text{ } +
\end{alignedat}
}}}#
pub fn infix_to_postfix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix {
match op {
"(" => {
stack.push("(");
}
")" => {
while let Some(temp) = stack.pop() {
if temp == "(" {
break;
}
out.push(temp);
}
}
_ => {
if let Some(priority) = get_priority(op) {
while let Some(temp) = stack.last().copied() {
if temp == "(" || priority > get_priority(temp).unwrap() {
break;
}
out.push(temp);
unsafe {
stack.set_len(stack.len() - 1);
}
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out
}
public static String[] infixToPostfix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (final String op : infix) {
switch (op) {
case "(":
stack.push("(");
break;
case ")":
while (!stack.isEmpty()) {
final String temp = stack.pop();
if (temp.equals("(")) {
break;
}
out.add(temp);
}
break;
default: {
final int priority = getPriority(op);
if (priority > 0) {
while (!stack.isEmpty()) {
final String temp = stack.peek();
if (temp.equals("(") || priority > getPriority(temp)) {
break;
}
out.add(stack.pop());
}
stack.push(op);
} else {
out.add(op);
}
}
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
return out.toArray(new String[out.size()]);
}
function infixToPostfix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (const op of infix) {
switch (op) {
case "(":
stack.push("(");
break;
case ")":
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const temp = stack.pop()!;
if (temp === "(") {
break;
}
out.push(temp);
}
break;
default: {
const priority = getPriority(op);
if (priority > 0) {
while (stack.length > 0) {
const temp = stack[stack.length - 1];
if (temp === "(" || priority > getPriority(temp)) {
break;
}
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
return out;
}
func InfixToPostfix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for _, op := range infix {
switch op {
case "(":
stack = stack.Push("(")
case ")":
for len(stack) > 0 {
var temp string
stack, temp = stack.Pop()
if temp == "(" {
break
}
out = append(out, temp)
}
default:
{
priority := getPriority(op)
if priority > 0 {
for len(stack) > 0 {
temp := stack[len(stack)-1]
if temp == "(" || priority > getPriority(temp) {
break
}
var e string
stack, e = stack.Pop()
out = append(out, e)
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
return out
}
pub fn infix_to_prefix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix.iter().rev() {
match op {
")" => {
stack.push(")");
}
"(" => {
while let Some(temp) = stack.pop() {
if temp == ")" {
break;
}
out.push(temp);
}
}
_ => {
if let Some(priority) = get_priority(op) {
while let Some(temp) = stack.last().copied() {
if temp == ")" || priority > get_priority(temp).unwrap() {
break;
}
out.push(temp);
unsafe {
stack.set_len(stack.len() - 1);
}
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out.reverse();
out
}
public static String[] infixToPrefix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (int i = infix.length - 1; i >= 0; --i) {
final String op = infix[i];
switch (op) {
case ")":
stack.push(")");
break;
case "(":
while (!stack.isEmpty()) {
final String temp = stack.pop();
if (temp.equals(")")) {
break;
}
out.add(temp);
}
break;
default: {
final int priority = getPriority(op);
if (priority > 0) {
while (!stack.isEmpty()) {
final String temp = stack.peek();
if (temp.equals(")") || priority > getPriority(temp)) {
break;
}
out.add(stack.pop());
}
stack.push(op);
} else {
out.add(op);
}
}
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
Collections.reverse(out);
return out.toArray(new String[out.size()]);
}
function infixToPrefix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (let i = infix.length - 1;i >= 0;i--) {
const op = infix[i];
switch (op) {
case ")":
stack.push(")");
break;
case "(":
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const temp = stack.pop()!;
if (temp === ")") {
break;
}
out.push(temp);
}
break;
default: {
const priority = getPriority(op);
if (priority > 0) {
while (stack.length > 0) {
const temp = stack[stack.length - 1];
if (temp === ")" || priority > getPriority(temp)) {
break;
}
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
out.reverse();
return out;
}
type stack []string
func (s stack) Push(v string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func InfixToPrefix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for i := len(infix) - 1; i >= 0; i-- {
op := infix[i]
switch op {
case ")":
stack = stack.Push(")")
case "(":
for len(stack) > 0 {
var temp string
stack, temp = stack.Pop()
if temp == ")" {
break
}
out = append(out, temp)
}
default:
{
priority := getPriority(op)
if priority > 0 {
for len(stack) > 0 {
temp := stack[len(stack)-1]
if temp == ")" || priority > getPriority(temp) {
break
}
var e string
stack, e = stack.Pop()
out = append(out, e)
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
out[i], out[j] = out[j], out[i]
}
return out
}
这样的实作方式会让中序式的基本计算顺序变成由右向左。例如 a - b - c 就会变成 (a - (b - c)),等同于 a - b + c,会跟原算式不相等。所以如果写出以上的程序那就错了。(许多网站提供的代码或是网页计算机就是这种有问题的)