后缀转中缀
给出由数字和四则运算符组成的后缀表达式，转换为中缀表达式，输出的时候如果有必要加上括号则括号要加上。
我想用栈来实现，但是判断是不是要加括号的时候不知道怎么判断了。
3 2 - 2 5 + * 5 9 - /，比如这个该怎么判断是否加括号，输出为(3-2)*(2+5)/(5-9)

[解决办法]

C/C++ code

string m(string str,char c){        if(str.size() == 1 || (str[str.size()-1] != '+' && str[str.size()-1] != '-' && str[str.size()-1] != '*' && str[str.size()-1] != '/'))        return str;    else if(str.size() == 3)    {        string st(str);        st[0] = str[0];        st[1] = str[2];        st[2] = str[1];        if((c == '*' || c == '/') && (str[str.size()-1] != '*' && str[str.size()-1] != '/'))        {            st = "(" + st + ")";        }        return st;    }    else    {        string s2,s1;        if(str[str.size()-2]-'0' >=0 && str[str.size()-2]-'0' <9)        {            string str2 = str.substr(str.size()-2,1);            string str1 = str.substr(0,str.size()-2);                s2 = m(str2,str[str.size()-1]);            s1 = m(str1,str[str.size()-1]);        }else        {            string str2 = str.substr(str.size()-4,3);            string str1 = str.substr(0,str.size()-4);                s2 = m(str2,str[str.size()-1]);            s1 = m(str1,str[str.size()-1]);        }        string s =  s1 + str[str.size()-1] + s2;        if(c != '#')            return s;        else         if((c == '*' || c == '/') && (str[str.size()-1] != '*' && str[str.size()-1] != '/'))        {            return "(" + s + ")";        }        else            return s;    }}void main(){    string st = "32-25+*59-/";    cout<<m(st,'#')<<endl;        system("pause");}
[解决办法]
C/C++ code
#include <stdio.h>#include <stdlib.h>#include <string.h>#define RETURN  0x0d // \r#define NEWLINE 0x0a // \n#define SPACE   0x20#define TAB     0x09 // \t#define SEPERATOR   0x2c // ,#define ISOPERATOR(c)   \        (('+' == c) || ('-' == c) || ('*' == c) || ('/' == c))#define ISSEPERATOR(c)  \        ((SEPERATOR == c) || (SPACE == c) || (TAB == c))#define PRIORITY(op)    \        ((('*' == op) || ('/' == op)) ? (short)1 : (short)0)typedef struct _ITEM{    char* expr;    short priority;    short merged;    struct _ITEM* next;} TItem, *PTItem;void merge_link(PTItem phdr, char op){    if(! phdr || ! phdr->next) exit(-1);    PTItem pn1 = phdr->next;    PTItem pn2 = pn1->next;    if(! pn2) exit(-1);    pn2->expr = (char*)realloc(pn2->expr, strlen(pn2->expr) + sizeof(char) + strlen(pn1->expr) + 4 + 1);    if(PRIORITY(op) > pn2->priority)    {                        char* p = pn2->expr + strlen(pn2->expr);        *(p + 1) = 0x00;        while(p > pn2->expr)        {            *p = *(p - 1);            p --;        }        *(pn2->expr) = '(';        strcat(pn2->expr, ")");    }    *(pn2->expr + strlen(pn2->expr) + 1) = 0x00;    *(pn2->expr + strlen(pn2->expr)) = op;    pn2->priority = PRIORITY(op);    pn2->merged = 1;        if(PRIORITY(op) > pn1->priority)    {        if(pn1->merged) strcat(pn2->expr, "(");        strcat(pn2->expr, pn1->expr);        if(pn1->merged) strcat(pn2->expr, ")");    }    else    {        strcat(pn2->expr, pn1->expr);    }    phdr->next = pn2;        free(pn1->expr);    free(pn1);}void build_link(PTItem phdr, char* _expr){    if(! phdr || ! _expr) exit(-1);    char* p = _expr, *q = p;    while(*p)    {        if(ISOPERATOR(*p))        {            merge_link(phdr, *p);            q = p + 1;            if(*q)            {                p ++;                q ++;            }        }        else if(ISSEPERATOR(*p))        {            PTItem pitem = (PTItem)malloc(sizeof(TItem));            memset(pitem, 0, sizeof(TItem));            pitem->expr = (char*)malloc(sizeof(char) * (p - q + 1));            strncpy(pitem->expr, q, p - q);            pitem->expr[p - q] = 0x00;            q = p + 1;            pitem->next = phdr->next;            phdr->next = pitem;            pitem->priority = 0;        }        p ++;    }    printf("expression is: %s\n", phdr->next->expr);}void free_link(PTItem phdr){    PTItem p = phdr->next;    while(p)    {        phdr->next = p->next;        if(p->expr) free(p->expr);        free(p);        p = phdr->next;    }}int main(void){    char expr[256] = { 0 };    printf("Please input expression:\neg: 12,3,+,6,4,-,*,3,/\n");        int i = 0;    for(i = 0; i < 255; i ++)    {        scanf("%c", &expr[i]);        if(NEWLINE == expr[i])        {            expr[i] = 0x00;            if(i && (RETURN == expr[i - 1]))                expr[i - 1] = 0x00;            break;        }    }        for(i = strlen(expr) - 1; i >= 0; i --)    {        if(ISOPERATOR(expr[i])) break;                expr[i] = 0x00;    }    if(*expr)    {        TItem hdr = { 0 };                build_link(&hdr, expr);        free_link(&hdr);    }    fflush(stdin);    getchar();    return 0;}