程式扎記

前言:
Infix 是人類使用的算術表示方法, 下面是 Wiki 對 Infix notation 的說明:

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2). It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity.

問題在於電腦程式要解析 Infix 的表示式有一定的困難度, 因此存在了 Infix -> Postfix 的轉換. 因為相對 Infix 來說, Postfix 對電腦程式來說容易解析.

範例代碼:
下面代碼為 C 語言的 Infix->Postfix 轉換範例代碼:

view plaincopy to clipboardprint?
#include <stdlib.h>
#include <stdio.h>
#include <string.h>   
  
#define bool int  
#define true 1  
#define false 0  
  
char operators[] = "+-*/^";  
  
struct Stk_Chr  
{  
    int pt;  
    char buffer[256];  
} Stack_Chr;  
  
int Stack_Chr_Size(struct Stk_Chr *pstack)  
{  
    return pstack->pt;  
}  
  
void Stack_Chr_Init(struct Stk_Chr *pstack)  
{  
    pstack->pt =0;  
    memset(pstack->buffer,0,sizeof(char)*256);  
}  
  
bool Stack_Chr_Is_Empty(struct Stk_Chr *pstack)  
{  
    if(pstack->pt ==0)  
        return true;  
    return false;  
}  
  
bool Stack_Chr_Is_Full(struct Stk_Chr *pstack)  
{  
    if(pstack->pt >=255)  
        return true;  
    return false;  
}  
  
bool Stack_Chr_Push(struct Stk_Chr *pstack, char data)  
{  
    if(Stack_Chr_Is_Full(pstack))  
        return false;  
    pstack->buffer[pstack->pt] = data;  
    pstack->pt++;  
    return true;  
}  
  
bool Stack_Chr_Pop(struct Stk_Chr *pstack, char *data)  
{  
    if(Stack_Chr_Is_Empty(pstack))  
        return false;  
    pstack->pt--;  
    *data = pstack->buffer[pstack->pt];  
  
    return true;  
}  
  
bool Stack_Chr_PopOut(struct Stk_Chr *pstack)  
{  
    if(Stack_Chr_Is_Empty(pstack))  
        return false;  
    pstack->pt--;  
  
    return true;  
}  
  
bool Stack_Chr_Peer(struct Stk_Chr *pstack, char *data)  
{  
    if(Stack_Chr_Is_Empty(pstack))  
        return false;  
    *data = pstack->buffer[(pstack->pt)-1];  
    return true;  
}  
  
bool isOperator(char op)  
{  
    char *pch;  
    pch = strchr(operators, op);  
    if(pch!=NULL)  
    {  
        return true;  
    }  
    else  
    {  
        return false;  
    }  
}  
  
bool isSubexpr(char op)  
{  
    if(op == '(') return true;  
    return false;  
}  
  
int priority(char op)  
{  
  switch(op) {  
  case '+': case '-': return 1;  
  case '*': case '/': return 2;  
  default:            return 0;  
  }  
}  
  
char* InfixToPostfix(char* infixExp, char* opostfixExp, int s, int e)  
{  
    int i, j, k, idx=0;  
    struct Stk_Chr stack;   
    Stack_Chr_Init(&stack);  
  
    char tchr;  
    char *postfixExpr = (char*)malloc(100*sizeof(char));  
    for(i=s; i
    {  
        if(infixExp[i]== ' ') continue;  
        else if(isOperator(infixExp[i]))  
        {  
            if(Stack_Chr_Is_Empty(&stack)==1)  
            {  
                Stack_Chr_Push(&stack, infixExp[i]);  
            }  
            else  
            {  
                Stack_Chr_Peer(&stack, &tchr);  
                if(priority(infixExp[i]) > priority(tchr))  
                {  
                    Stack_Chr_Push(&stack, infixExp[i]);  
                }  
                else  
                {  
                    postfixExpr[idx] = tchr;  
                    Stack_Chr_PopOut(&stack);  
                    idx+=1;  
                    Stack_Chr_Push(&stack, infixExp[i]);  
                }  
            }  
        }  
        else if(isSubexpr(infixExp[i]))  
        {  
            int cnt = 1;  
            int si = i+1;  
            char ichr;  
            while(cnt > 0 && si < strlen(infixExp))  
            {  
                ichr = infixExp[si];  
                if(ichr == '(') cnt++;  
                else if(ichr==')') cnt--;  
                si++;  
            }  
            if(cnt == 0)  
            {  
                si--;  
                InfixToPostfix(infixExp, postfixExpr, i+1, si);  
                idx = strlen(postfixExpr);  
                i = si;  
            }  
            else  
            {  
                printf("Illegal infix expression!\n");  
                return;  
            }  
        }  
        else  
        {  
            postfixExpr[idx]=infixExp[i];  
            idx++;  
        }  
    }  
    while(Stack_Chr_Is_Empty(&stack)==0)  
    {  
        Stack_Chr_Pop(&stack, &tchr);  
        postfixExpr[idx] = tchr;  
        idx++;  
    }  
    strcat(opostfixExp, postfixExpr);  
    free(postfixExpr);  
    return opostfixExp;  
}  
  
int main()  
{  
    int i, j, k, idx=0;  
    char expr[100];  
    char *postfixExpr = (char*)malloc(100*sizeof(char));;  
    memset(postfixExpr,0,sizeof(char)*100);  
    printf("Give Infix expression: ");  
    scanf("%s", expr);  
    InfixToPostfix(expr, postfixExpr, 0, strlen(expr));  
    printf("\t[Info] Postfix=%s\n", postfixExpr);  
    free(postfixExpr)
    return 0;  
}  

執行結果:

Give Infix expression: a*(b+c)+d*e
[Info] Postfix=abc+*de*+

上面再 stdin 輸入 Infix 表示式 "a*(b+c)+d*e" 得到的 Postfix 表示式為 "abc+*de*+". 有關 Java 版本的 Infix->Postfix 轉換可以參考:
[ Data Structures with Java ] Section 14.5 : Infix Expression Evaluation

補充說明:
* Algorithm Gossip: 中序式轉後序式（前序式）

平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理解，但由於電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以必須將中序表示式轉換為另一種表示方法...

程式扎記

標籤

2013年2月22日星期五

[C 範例代碼] Infix to Postfix translation (Recursive approach)

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

檢舉濫用情形

學習筆記

標籤

2013年2月22日 星期五