# 中序式轉後序式

December 12, 2021

## 解法思路

1. a + b * d + c / d
2. ((a + (b * d)) + (c / d))
3. a b d * + c d / +

``````Procedure Postfix(infix) [
Loop [
op = infix(i)
case [
:x = '\0':
while (stack not empty)
// output all elements in stack
end
return
:x = '(':
// put it into stack
:x is operator:
while (priority(stack[top]) >=
priority(op)) [
// out a element from stack
]
// save op into stack
:x = ')':
while ( stack(top) != '(' ) [
// out a element from stack
]
top = top - 1  // not out '(
:else:
// output current op
]
i++;
]
]
``````

( ( -
a ( a
+ (+ a
b (+ ab
) - ab+
* * ab+
( *( ab+
c *( ab+c
+ *(+ ab+c
d *(+ ab+cd
) * ab+cd+
- - ab+cd+*

## 程式實作

``````#include <stdio.h>
#include <stdlib.h>

#define MAX 80

void inToPostfix(char*, char*); // 中序轉後序
int priority(char); // 運算子優先權

int main(void) {
char infix[MAX] = {'\0'};
char postfix[MAX]= {'\0'};

printf("中序運算式：");
scanf("%s", infix);
inToPostfix(infix, postfix);

int i;
for(i = 0; postfix[i] != '\0'; i++) {
printf("%c", postfix[i]);
}

return 0;
}

void inToPostfix(char* infix, char* postfix) {
char stack[MAX] = {'\0'};
int i, j, top;
for(i = 0, j = 0, top = 0; infix[i] != '\0'; i++) switch(infix[i]) {
case '(':              // 運算子堆疊
stack[++top] = infix[i];
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(infix[i])) {
postfix[j++] = stack[top--];
}
stack[++top] = infix[i]; // 存入堆疊
break;
case ')':
while(stack[top] != '(') { // 遇 ) 輸出至 (
postfix[j++] = stack[top--];
}
top--;  // 不輸出 (
break;
default:  // 運算元直接輸出
postfix[j++] = infix[i];
}
while(top > 0) {
postfix[j++] = stack[top--];
}
}

int priority(char op) {
switch(op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
default:            return 0;
}
}
``````
``````import java.util.*;
import static java.lang.System.out;

public class Infix {
private static int priority(char c) {
return c == '+' || c == '-' ? 1 : c == '*' || c == '/' ? 2 : 0;
}

private static String toPostfix(String infix, boolean isPost) {
String expr = isPost ?
infix : new StringBuffer(infix).reverse().toString();
StringBuilder output = new StringBuilder();
char toStack = isPost ? '(' : ')';
char toOutput = isPost ? ')' : '(';
for(char c : expr.toCharArray()) {
if(c == toStack) { stack.add(c); }
else if("+-*/".indexOf(c) != -1) {
while(!stack.isEmpty() &&
priority(stack.getLast()) >= priority(c)) {
output.append(stack.removeLast());
}
}
else if(c == toOutput) {
while(stack.getLast() != toStack) {
output.append(stack.removeLast());
}
stack.removeLast();
}
else { output.append(c); }
}

while(!stack.isEmpty()) { output.append(stack.removeLast()); }

return isPost ? output.toString() : output.reverse().toString();
}

public static String toPostfix(String infix) {
}

public static String toPrefix(String infix) {
}

public static void main(String[] args) {
String infix = "(a+b)*(c+d)";
out.println(toPostfix(infix));
out.println(toPrefix(infix));
}
}
``````
``````def priority(op):
return 1 if op in "+-" else 2 if op in "*/" else 0

def toPostfix(infix, isPost = True):
toStack, toOutput = ('(', ')') if isPost else (')', '(')

def procOpt(c, stack, output):
if stack == "" or priority(stack[-1]) < priority(c):
return (stack + c, output)
else:
return procOpt(c, stack[0:-1], output + stack[-1])

def procPhs(stack, output):
if stack[-1] == toStack:
return (stack[0:-1], output)
else:
return procPhs(stack[0:-1], output + stack[-1])

def procExpr(expr, stack = "", output = ""):
if expr == "":
return output + stack[::-1]
elif expr[0] == toStack:
return procExpr(expr[1:], stack + expr[0], output)
elif expr[0] in "+-*/":
return procExpr(expr[1:], *procOpt(expr[0], stack, output))
elif expr[0] == toOutput:
return procExpr(expr[1:], *procPhs(stack, output))
else:
return procExpr(expr[1:], stack, output + expr[0])

output = procExpr(infix if isPost else infix[::-1])
return output if isPost else output[::-1]

def toPrefix(infix):

infix = "(a+b)*(c+d)"
print(toPostfix(infix))
print(toPrefix(infix))
``````
``````def priority(op: Char) = op match {
case '+' | '-' => 1
case '*' | '/' => 2
case _         => 0
}

def toPostfix(infix: String, isPost: Boolean = true) = {
val (toStack, toOutput) = if(isPost) ('(', ')') else (')', '(')

def procOpt(c: Char, stack: String, output: String): (String, String) = {
if(stack == "" || priority(stack.last) < priority(c)) {
(stack + c, output)
} else procOpt(c, stack.init, output + stack.last)
}

def procPhs(stack: String, output: String): (String, String) = {
if(stack.last == toStack) (stack.init, output)
else procPhs(stack.init, output + stack.last)
}

def procExpr(expr: String, so: (String, String) = ("", "")): String = {
val (stack, output) = so
if(expr == "") {
output + stack.reverse
} else if(expr.head == toStack) {
} else if(expr.head == toOutput) {
procExpr(expr.tail, procPhs(stack, output))
} else procExpr(expr.tail, (stack, output + expr.head))
}

val output = procExpr(if(isPost) infix else infix.reverse)
if(isPost) output else output.reverse
}

def toPrefix(infix: String) = toPostfix(infix, false)

val infix = "(a+b)*(c+d)"
println(toPostfix(infix))
println(toPrefix(infix))
``````
``````def priority(op)
"+-".include?(op) ? 1 : "*/".include?(op) ? 2 : 0
end

def toPostfix(infix, isPost = true)
toStack, toOutput = isPost ? ['(', ')'] : [')', '(']

procOpt = ->(c, stack, output) {
if stack == "" || priority(stack[-1]) < priority(c)
[stack + c, output]
else
procOpt.call(c, stack[0...-1], output + stack[-1])
end
}

procPhs = ->(stack, output) {
if stack[-1] == toStack
[stack[0...-1], output]
else
procPhs.call(stack[0...-1], output + stack[-1])
end
}

procExpr = ->(expr, stack = "", output = "") {
if expr == ""
output + stack.reverse
elsif expr[0] == toStack
procExpr.call(expr[1..-1], stack + expr[0], output)
elsif "+-*/".include? expr[0]
procExpr.call(expr[1..-1], *procOpt.call(expr[0], stack, output))
elsif expr[0] == toOutput
procExpr.call(expr[1..-1], *procPhs.call(stack, output))
else
procExpr.call(expr[1..-1], stack, output + expr[0])
end
}

output = procExpr.call(isPost ? infix : infix.reverse)
isPost ? output : output.reverse
end

def toPrefix(infix)
toPostfix(infix, false)
end

infix = "(a+b)*(c+d)"
puts(toPostfix(infix))
puts(toPrefix(infix))
``````
``````Array.prototype.getLast = function() {
return this[this.length - 1];
};

Array.prototype.isEmpty = function() {
return this.length == 0;
};

function priority(c) {
return c === '+' || c === '-' ? 1 : c === '*' || c === '/' ? 2 : 0;
}

function toPostfix(infix, isPost) {
isPost = isPost === undefined ? true : false;
var expr = isPost ? infix.split('') : infix.split('').reverse();
var stack = [];
var output = [];
var toStack = isPost ? '(' : ')';
var toOutput = isPost ? ')' : '(';
expr.forEach(function(c) {
if(c === toStack) { stack.push(c); }
else if('+-*/'.indexOf(c) !== -1) {
while(!stack.isEmpty() &&
priority(stack.getLast()) >= priority(c)) {
output.push(stack.pop());
}
stack.push(c);
}
else if(c === toOutput) {
while(stack.getLast() !== toStack) {
output.push(stack.pop());
}
stack.pop();
}
else { output.push(c); }
});

while(!stack.isEmpty()) { output.push(stack.pop()); }

return isPost ? output.join('') : output.reverse().join('');
}

function toPrefix(infix) {
}

var infix = "(a+b)*(c+d)";
print(toPostfix(infix));
print(toPrefix(infix));
``````
``````priority op = if op `elem` "+-" then 1
else if op `elem` "*/" then 2
else 0

toPfix inf isPost = if isPost then output else reverse output
where
(toStack, toOutput) = if isPost then ('(', ')') else (')', '(')
output = procExpr (if isPost then inf else reverse inf) ("", "")
procOpt c stack output =
if stack == "" || (priority \$ last stack) < priority c
then (stack ++ [c], output)
else procOpt c (init stack) (output ++ [last stack])
procPhs stack output =
if last stack == toStack then (init stack, output)
else procPhs (init stack) (output ++ [last stack])
procExpr expr so =
if expr == ""
then output ++ (reverse stack)
then procExpr tail (stack ++ [head], output)
then procExpr tail \$ procOpt head stack output