前中後序運算式互轉

雖然是很簡單的練習，
還是想了一整天才寫出來@@;

中序式轉前後序：

#include <cstring>
#include <iostream>
using namespace std;

namespace Exp
{
    int   d;                            //掃瞄方向
    char  in[512], out[512], *o;        //用來存放輸出結果
    char* exp (char*,char=2);           //執行前後序轉換
    char* postfix (char* s) 
    {
        o=out; d=1; exp (s); *o=0;
        return out;
    }
    char* prefix (char* s)
    {
        strcpy (in+1, s); *in=0;
        o=out; d=-1; exp (in+strlen(s)); *o=0;
        return strrev (out);
    }
};
char* Exp::exp (char* s, char p)
{   
    p? s=exp (s, p-1): isalpha(*s)? (*o++=*s), s+=d: 0; 
    char c = *s;
    if (2 == p) while (c=='+'||c=='-') {s=exp(s+d,p-1); *o++=c; c=*s;}
    if (1 == p) while (c=='*'||c=='/') {s=exp(s+d,p-1); *o++=c; c=*s;}
    if (0 == p && c==") ("[d+1]) {s=exp(s+d); if ("( )"[d+1]==*s) s+=d;}
    return s;
}

int main (/* daviddr 091022 */)
{
    #define _ cout << endl <<

    _ "後序:\n";
    _ Exp::postfix ("a*b+c/(d-e-f)*g/h");
    _ Exp::postfix ("a*(b+c)/d");
    _ Exp::postfix ("a+b*c");

    _ "\n前序:\n";
    _ Exp::prefix ("a*b+c/(d-e-f)*g/h");
    _ Exp::prefix ("a*(b+c)/d");
    _ Exp::prefix ("a+b*c");
}

前序式轉中後序：

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

char* post (char* p)
{
    char c = *p; c? isalpha(c)? putchar (*p++): 
    (p = post (post (p+1)), putchar(c)): int(p=0);
    return p;    
}

bool bPara (char a, char b) 
{
    return (a=='*'||a=='/') && (b=='+'||b=='-');
}

char* infix (char* p)
{
    #define P putchar
    #define R(n) (bPara (c, p[n])?\
    P('('), p=infix (p+n), P(')'): int(p=infix (p+n)))
    char c = *p; c? isalpha(c)? 
    P(*p++): (R(1),P(c),R(0)): int(p=0);
    return p;    
}

int main (/*daviddr 0907*/)
{
    #define _ puts(""); 
    _ post ("-*A+BCD");
    _ post ("+-+-*ABCD*/EFGH");
    _ post ("-/*a+BCD*EF");
    _
    _ infix ("-*A+BCD");
    _ infix ("+-+-*ABCD*/EFGH");
    _ infix ("-/*a+BCD*EF");
}

後序式轉前中序：

暫缺...

堆疊解法：

#define ef else if

struct Item { char op; double val; };               //op=1 時, Item 為數值
                                                    //否則為算符, 編號即為 op
Item   s1[512], s2[512];                            //存放中序與後序式
int    n1, n2;                                      //記錄 s1,s2 的元素個數
int    pri[255] = {-1};                             //運算子優先權

double get_postfix (char* s)
{
    char   c, *p;
    double v[128];

    for (s1[0].op= n1= n2= 0; *s; s++)
    {
        while (' '==*s) s++;                            //略過空白
        c = isdigit(*s)? 1: *s;
        while (pri[c] <= pri[s1[n1].op] && 
               '('!=s1[n1].op)
            s2[++n2] = s1[n1--];                        //將後序式放入 s2
        if (')'==c) n1--;                               //將 '(' pop 掉
        ef (1 == (s1[++n1].op=c))                       //若 token 為數值
            s1[n1].val = strtod (s, &p), s=p-1;         //則將值存入 val 裡                    
    }
    while (n1>0) s2[++n2] = s1[n1--];                   //將後序式放入 s2

    for (int i=1; i<=n2; i++)
        if (1 == (c=s2[i].op)) v[++n1] = s2[i].val;
        else {
            if (c=='+') v[n1-1] += v[n1];
            ef (c=='-') v[n1-1] -= v[n1];
            ef (c=='*') v[n1-1] *= v[n1];
            ef (c=='/') v[n1-1] /= v[n1];
            n1--;
        }
    return v[1];
}

void print_postfix()
{
    for (int i=1; i<=n2; i++)
        if (s2[i].op == 1) cout <<' '<< s2[i].val;
        else cout <<' '<< s2[i].op;
}

int main (/* daviddr 081113 */)
{
    pri['(']=(pri[1]=(pri['*']=pri['/']=
    (pri['+']=pri['-']=1)+1)+1)+1;   
    char exp[512];
    cout <<"請輸入中序運算式: ";
    cin.getline (exp, 512);                           //輸入算式
    cout <<"答案為: " << get_postfix (exp);           //計算後序式並求解
    cout <<"\n轉成後序式: "; print_postfix();
    return system ("pause");
}

若只是要「印出」後序式，那麼可以再簡化：

int pri[255] = {-1};                             //運算子優先權

void print_postfix (char* p)
{   
    char *end, s[512] = {0};   
    int n = 0;
    for (; *p; p++) {   
        while (' '==*p) p++;
        if (isdigit(*p)) {
            cout <<' '<< strtod (p, &end);
            p = end-1;
        } else {
            while (pri[*p] <= pri[s[n]] && '('!=s[n])
                cout <<' '<< s[n--];
            if (*p!=')') s[++n] = *p; else n--;
        }     
    }while (n>0) cout <<' '<< s[n--];
}

int main ()
{
    pri['(']=(pri[1]=(pri['*']=pri['/']=(pri['+']=pri['-']=1)+1)+1)+1;  
    char exp[512];
    cout <<"請輸入中序式："; cin.getline (exp, 512);
    cout <<"\n轉成後序式: "; print_postfix (exp);
    return system ("PAUSE");
}

最上方的 namespace Exp 原型為：

#define ef else if

class Exp
{
    char*  p;                       //指向欲處理的符號
    double add ()
    {
        double v = mul();
        for (char c=*p; c=='+' || c=='-'; c=++*p)
            if ('+'==c) v += mul();
            ef ('-'==c) v -= mul();
        return v;
    }
    double mul ()
    {
        double v = pow();
        while (char c=*p; c=='%' || c=='*' || c=='/'; c=++*p)
            if ('%'==c) v = int(v)%(int)pow();
            ef ('*'==c) v *= pow();
            ef ('/'==c) v /= pow();
        return v;
    }
    double pow ()
    {
        double v = par();
        while (*p=='^') {p++; v = ::pow (v,par());}
        return v;   
    }
    double par ()
    {
        while (' '==*p) p++;
        double v = strtod (p, &p);
        if (*p == '(') {
            p++; v = add ();
            if (*p == ')') p++;
            else cout << "缺少右括弧!";            
        }
        while (' '==*p) p++;
        return v;
    }
public:
    double cal (char* s) {p=s; return add();}
};

int main ()
{
    char s[128];
    cout << "輸入運算式: "; 
    cin.get (s, 128);
    cout << Exp().cal(s);  
}