說明
平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理
解，但由於電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以必須將中序表示式轉換為另一種表示方
法。
可以將中序表示式轉換為後序（Postfix）表示式，後序表示式又稱之為逆向波蘭表示式（Reverse polish notation），它是由波蘭的數學家盧卡謝維奇提出，例如(a+b)*(c+d)這個式子，表示為後序表示式時是ab+cd+*。
解法
用手算的方式來計算後序式相當的簡單，將運算子兩旁的運算元依先後順序全括號起來，然後將所有的右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉所有的左括號就可以完成後序表示式，例如：
a+b*d+c/d => ((a+(b*d))+(c/d)) -> abd*+cd/+
如果要用程式來進行中序轉後序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用迴圈，取出中序式的字元，遇運算元直接輸出；堆疊運算子與左括號；
堆疊中運算子優先順序大於讀入的運算子優先順序的話，直接輸出堆疊中的運算子，再將讀入的運算子置入堆疊；遇右括號輸出堆疊中的運算子至左括號。
演算法
以下是虛擬碼的運算法，\0表示中序式讀取完畢：
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+b)*(c+d)這個式子，依演算法的輸出過程如下：
| OP |
STACK |
OUTPUT |
| ( |
( |
- |
| 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
int postfix(char*); // 中序轉後序
int priority(char); // 決定運算子優先順序
int main(void) {
char input[MAX];
printf("輸入中序運算式：");
scanf("%s", input);
postfix(input);
return 0;
}
int postfix(char* infix) {
char stack[MAX] = {'\0'};
int i = 0;
int top = 0;
while(1) {
switch(infix[i]) {
case '\0':
while(top > 0) {
printf("%c", stack[top]);
top--;
}
printf("\n");
return 0;
// 運算子堆疊
case '(':
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = infix[i];
}
break;
case '+': case '-': case '*': case '/':
while(priority(stack[top]) >= priority(infix[i])) {
printf("%c", stack[top]);
top--;
}
// 存入堆疊
if(top < (sizeof(stack) / sizeof(char))) {
top++;
stack[top] = infix[i];
}
break;
// 遇 ) 輸出至 (
case ')':
while(stack[top] != '(') {
printf("%c", stack[top]);
top--;
}
top--; // 不輸出(
break;
// 運算元直接輸出
default:
printf("%c", infix[i]);
break;
}
i++;
}
}
int priority(char op) {
int p;
switch(op) {
case '+': case '-':
p = 1; break;
case '*': case '/':
p = 2; break;
default:
p = 0; break;
}
return p;
}
import java.util.*;
public class InFix {
private static int priority(char op) {
switch(op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
default: return 0;
}
}
public static String toPostfix(String expr) {
LinkedList<Character> stack = new LinkedList<Character>();
stack.add('\u0000'); // 堆疊底部為空字元
StringBuffer buffer = new StringBuffer();
for(char c : expr.toCharArray()) {
switch(c) {
// 運算子堆疊
case '(':
stack.add(c);
break;
case '+': case '-': case '*': case '/':
while(priority(stack.getLast()) >= priority(c)) {
buffer.append(stack.removeLast());
}
// 存入堆疊
stack.add(c);
break;
// 遇 ) 輸出至 (
case ')':
while(stack.getLast() != '(') {
buffer.append(stack.removeLast());
}
stack.removeLast(); // 不輸出(
break;
// 運算元直接輸出
default:
buffer.append(c);
}
}
while(stack.getLast() != '\u0000') {
buffer.append(stack.removeLast());
}
return buffer.toString();
}
public static String toPrefix(String expr) {
LinkedList<Character> stack = new LinkedList<Character>();
stack.add('\u0000'); // 堆疊底部為空字元
StringBuffer buffer = new StringBuffer();
for(char c : new StringBuffer(expr).reverse()
.toString().toCharArray()) {
switch(c) {
// 運算子堆疊
case ')':
stack.add(c);
break;
case '+': case '-': case '*': case '/':
while(priority(stack.getLast()) >= priority(c)) {
buffer.append(stack.removeLast());
}
// 存入堆疊
stack.add(c);
break;
// 遇 ( 輸出至 )
case '(':
while(stack.getLast() != ')') {
buffer.append(stack.removeLast());
}
stack.removeLast(); // 不輸出)
break;
// 運算元直接輸出
default:
buffer.append(c);
}
}
while(stack.getLast() != '\u0000') {
buffer.append(stack.removeLast());
}
return buffer.reverse().toString();
}
public static void main(String[] args) {
String infix = "(a+b)*(c+d)";
System.out.println(InFix.toPostfix(infix));
System.out.println(InFix.toPrefix(infix));
}
}
def priority(op):
if op in ['+', '-']:
return 1
elif op in ['*', '/']:
return 2
else:
return 0
def toPostfix(infix):
stack = ['']
buffer = []
for c in infix:
if c == '(':
stack.append(c)
elif c in "+-*/":
while priority(stack[-1]) >= priority(c):
buffer.append(stack.pop())
stack.append(c)
elif c == ')':
while stack[-1] != '(':
buffer.append(stack.pop())
stack.pop()
else:
buffer.append(c)
while stack[-1] != '':
buffer.append(stack.pop())
return buffer
def toPrefix(infix):
stack = ['']
buffer = []
for c in infix[::-1]:
if c == ')':
stack.append(c)
elif c in "+-*/":
while priority(stack[-1]) >= priority(c):
buffer.append(stack.pop())
stack.append(c)
elif c == '(':
while stack[-1] != ')':
buffer.append(stack.pop())
stack.pop()
else:
buffer.append(c)
while stack[-1] != '':
buffer.append(stack.pop())
buffer.reverse()
return buffer
infix = "(a+b)*(c+d)"
print(toPostfix(infix))
print(toPrefix(infix))
import scala.collection.mutable.ListBuffer
object InFix {
private def priority(op: Char) = {
op match {
case '+'|'-' => 1
case '*'|'/' => 2
case _ => 0
}
}
def toPostfix(expr: String) = {
val stack = new ListBuffer[Char]
stack + '\u0000'
val buffer = new ListBuffer[Char]
for(c <- expr) {
c match {
case '(' =>
stack + c
case '+'|'-'|'*'|'/' =>
while(priority(stack.last) >= priority(c)) {
buffer + stack.last
}
stack + c
case ')' =>
while(stack.last != '(') {
buffer + stack.remove(stack.length- 1)
}
stack.remove(stack.length - 1)
case _ => buffer + c
}
}
while(stack.last != '\u0000') {
buffer + stack.remove(stack.length - 1)
}
buffer.mkString
}
def toPrefix(expr: String) = {
val stack = new ListBuffer[Char]
stack + '\u0000'
val buffer = new ListBuffer[Char]
for(c <- expr.reverse) {
c match {
case ')' =>
stack + c
case '+'|'-'|'*'|'/' =>
while(priority(stack.last) >= priority(c)) {
buffer + stack.last
}
stack + c
case '(' =>
while(stack.last != ')') {
buffer + stack.remove(stack.length- 1)
}
stack.remove(stack.length - 1)
case _ => buffer + c
}
}
while(stack.last != '\u0000') {
buffer + stack.remove(stack.length - 1)
}
buffer.reverse.mkString
}
}
val infix = "(a+b)*(c+d)"
println(InFix.toPostfix(infix))
println(InFix.toPrefix(infix))
|