中序表達式轉換為逆波蘭表達式

中序表達式轉換為逆波蘭表達式，實現了基本的加減乘除以及括號的應用。

將一個普通的中序表達式轉換為逆波蘭表達式的一般算法是：首先需要分配2個棧，一個作為臨時存儲運算符的棧S1含一個結束符號），一個作為輸入逆波蘭式的棧S2空棧），S1棧可先放入優先級最低的運算符#，注意，中綴式應以此最低優先級的運算符結束。可指定其他字符，不一定非#不可。從中綴式的左端開始取字符，逐序進行如下步驟：1）若取出的字符是操作數，則分析出完整的運算數，該操作數直接送入S2棧2）若取出的字符是運算符，則將該運算符與S1棧棧頂元素比較，如果該運算符優先級大於S1棧棧頂運算符優先級，則將該運算符進S1棧，否則，將S1棧的棧頂運算符彈出，送入S2棧中，直至S1棧棧頂運算符低於不包括等於）該運算符優先級，則將該運算符送入S1棧。3）若取出的字符是“”，則直接送入S1棧棧頂。4）若取出的字符是“）”，則將距離S1棧棧頂最近的“”之間的運算符，逐個出棧，依次送入S2棧，此時拋棄“”。5）重復上面的1~4步，直至處理完所有的輸入字符6）若取出的字符是“#”，則將S1棧內所有運算符不包括“#”），逐個出棧，依次送入S2棧。完成以上步驟，S2棧便為逆波蘭式輸出結果。不過S2應做一下逆序處理。便可以按照逆波蘭式的計算方法計算了！

#include<iostream>
using namespace std;
#define MaxSize 100
#define MaxOp 7
struct{
    char ch;
    int pri;
}
lpri[] = {{'=',0},{'(',1},{'*',5},{'/',5},{'+',3},{'-',3},{')',6}},
rpri[] = {{'=',0},{'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}};
int leftpri(char op){
    int i;
    for(i=0;i<MaxOp;i++)
        if(lpri[i].ch == op)
            return lpri[i].pri;
}
int rightpri(char op){
    int i;
    for(i=0;i<MaxOp;i++)
        if(rpri[i].ch == op)
            return rpri[i].pri;
}
int InOp(char ch){
    if(ch == '(' || ch == ')' ||ch == '+' || ch == '-' || ch == '*' || ch == '/')
        return 1;
    else
        return 0;
}
int Precede(char op1,char op2){
    if(leftpri(op1) == rightpri(op2))
        return 0;
    else if(leftpri(op1) < rightpri(op2))
        return -1;
    else
        return 1;
}
void trans(char * exp,char postexp[]){
    struct{
        char data[MaxSize];
        int top;
    }op;
    int i=0;
    op.top=-1;
    op.top++;
    op.data[op.top]='=';
    while(* exp != '\0'){
        if(!InOp(* exp)){
            while(* exp >= '0' && * exp <= '9'){
                postexp[i++] = * exp;
                exp++;
                if(* exp == '.'){
                    postexp[i++] = * exp;
                    exp++;
                }
            }
            postexp[i++]='#';
        }
        else{
            switch(Precede(op.data[op.top],* exp)){
                case -1:
                    op.top++;
                    op.data[op.top] = * exp;
                    exp++;
                    break;
                case 0:
                    op.top--;
                    exp++;
                    break;
                case 1:
                    postexp[i++] = op.data[op.top];
                    op.top--;
                    break;
            }
        }
    }
    while(op.data[op.top] != '='){
        postexp[i++] = op.data[op.top];
        op.top--;
    }
    postexp[i] = '\0';
}
float calculated(char * postexp){
    struct{
        float data[MaxSize];
        int top;
    }st;
    float d,a,b,c,e,f;
    st.top=-1;
    while(* postexp != '\0'){
        switch(* postexp){
            case '+':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=a+b;
                st.top++;
                st.data[st.top]=c;
                break;
            case '-':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b-a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '*':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=a*b;
                st.top++;
                st.data[st.top]=c;
                break;
            case '/':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                if(a != 0){
                    c=b/a;
                    st.top++;
                    st.data[st.top]=c;
                }else{
                    cout<<"除零錯誤!"<<endl;
                    exit(0);
                }
                break;
            default:
                d=0;
                e=0;
                f=0;
                while(* postexp >= '0' && * postexp <= '9'){
                    d=10 * d+ *postexp-'0';
                    postexp++;
                    if(* postexp == '.'){
                        postexp++;
                        while(* postexp >= '0' && * postexp <= '9'){
                            f++;
                            e=e * 10 + *postexp-'0';
                            postexp++;
                        }
                        for(int i=0;i<f;i++)
                            e=e/10;
                    }
                }
                d=d+e;
                st.top++;
                st.data[st.top]=d;
                break;
        }
        postexp++;
    }
    return st.data[st.top];
}
int main(){
    char exp[MaxSize];
    char postexp[MaxSize];
    float value = 0;
    cout<<"請輸入你要計算的式子:";
    cin>>exp;
    trans(exp,postexp);
    cout<<"轉換成後綴表達式為:"<<postexp<<endl;
    value = calculated(postexp);
    cout<<"計算結果為:"<<value<<endl;
    return 0;
}

本文出自 “淡定的dreamer” 博客，請務必保留此出處http://idiotxl1020.blog.51cto.com/6419277/1288623