答案優(yōu)選這個(gè)問(wèn)題可以分為3部分

1、輸入一個(gè)字符串，將其格式化的儲(chǔ)存在一個(gè)數(shù)組中，以方便的記錄表達(dá)式中數(shù)和各個(gè)符號(hào)的出現(xiàn)順序
約定在數(shù)組中記錄時(shí)，每個(gè)數(shù)或符號(hào)用兩個(gè)整數(shù)來(lái)記錄
第一個(gè)整數(shù)記錄該位是什么東西，0表示是一個(gè)數(shù)，1表示是括號(hào)，2表示反括號(hào)，3、4、5、6分別表示乘除加減號(hào)
如果該位是一個(gè)數(shù)，那么第二個(gè)整數(shù)記錄著個(gè)數(shù)的具體取值，否則記錄該位的符號(hào)的ASCII碼
比如字符串"(1-23)"會(huì)被轉(zhuǎn)化成二位數(shù)組 , , , , }
這個(gè)轉(zhuǎn)化過(guò)程每什么技巧性，對(duì)原字符串各位順次判斷并處理即可
原先的字符串中可能出現(xiàn)一元運(yùn)算符正號(hào)'+'和負(fù)號(hào)'-'，為了處理方便，一律在其前面加個(gè)0，改寫成"0+..."或者"0-..."
另外為了之后轉(zhuǎn)化逆波蘭表達(dá)式方便，處理過(guò)程中會(huì)在轉(zhuǎn)化出的數(shù)組的首尾一律添加一對(duì)括號(hào)


2、將之前所提到的格式數(shù)組轉(zhuǎn)化為逆波蘭表達(dá)式
約定依然用二位數(shù)組記錄一個(gè)逆波蘭表達(dá)式，并且格式與之前的數(shù)組相同，除了沒(méi)有括號(hào)以外
比如逆波蘭表達(dá)式 1 2 - 35 +，會(huì)被記錄成{ , , , , }
轉(zhuǎn)化時(shí)，需要用一個(gè)棧
具體轉(zhuǎn)化操作如下：
順次處理格式數(shù)組的每一位，對(duì)其作判斷
如果該位是一個(gè)數(shù)或者是括號(hào)'('，，將其入棧
如果該位是乘號(hào)'*'或者除號(hào)'/'，不斷進(jìn)行出棧操作直到棧頂元素是個(gè)括號(hào)'('或者加號(hào)'+'或者減號(hào)'-'，然后將這個(gè)乘號(hào)或者除號(hào)入棧
如果該位是加號(hào)'+'或者減號(hào)'-'，不斷進(jìn)行出棧操作直到棧頂元素是個(gè)括號(hào)'('，然后將這個(gè)加號(hào)或者減號(hào)入棧

如果該位是反括號(hào)')'，那么不斷進(jìn)行出棧操作直到有一個(gè)括號(hào)'('出棧

在上述操作中，所有的出棧元素，除了括號(hào)'('以外，都被順次添加到所要生成的逆波蘭表達(dá)式的末尾
這樣就轉(zhuǎn)化出了一條逆波蘭表達(dá)式

3、對(duì)逆波蘭表達(dá)式求值
求值時(shí)，也需要用到一個(gè)棧
求值步驟如下：
順次處理逆波蘭表達(dá)式的每一位，對(duì)其作判斷
如果該位是一個(gè)數(shù)，將這個(gè)數(shù)入棧
如果該位是一個(gè)運(yùn)算符，那么連續(xù)進(jìn)行兩次出棧操作，可以得到棧頂?shù)膬蓚€(gè)元素，對(duì)這兩個(gè)元素用該位的運(yùn)算符做運(yùn)算，將所得的結(jié)果入棧
比如，如果當(dāng)時(shí)棧頂元素是3，次棧頂?shù)脑厥?，運(yùn)算符是減號(hào)'-'，那么連續(xù)兩次出棧得到3和2兩個(gè)元素，再將2-3的運(yùn)算結(jié)果1入棧
注意有些運(yùn)算符(減號(hào)和除號(hào))不符合交換律，因此運(yùn)算時(shí)必須是次棧頂元素在前、棧頂元素在后，順序不能反


當(dāng)每一位都處理完了之后，只要輸入的是一個(gè)合法的逆波蘭表達(dá)式，必然棧中只剩下一個(gè)元素，這個(gè)元素就是逆波蘭表達(dá)式求值的結(jié)果

源代碼如下：

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

void transform(char *str,int a[][2],int *n)
//將輸入的字符串轉(zhuǎn)化為格式化的數(shù)組以記錄輸入的表達(dá)式，str為輸入的字符串，a為目標(biāo)數(shù)組，n記錄數(shù)組a的大小
{
int i;
*n=1;
a[0][0]=1;
a[0][1]='(';//在表達(dá)式首添加一個(gè)括號(hào)
for (i=0;str[i];)
{
if (isdigit(str[i]))
{
a[*n][0]=0;
a[*n][1]=0;
while (isdigit(str[i]))
{
a[*n][1]=a[*n][1]*10+str[i]-'0';
i++;
}
}
else
{
if (str[i]=='(') a[*n][0]=1;
else if (str[i]==')') a[*n][0]=2;
else if (str[i]=='*') a[*n][0]=3;
else if (str[i]=='/') a[*n][0]=4;
else if (str[i]=='+' || str[i]=='-')
{
if (i==0 || (!isdigit(str[i-1]) && str[i-1]!=')'))
{
a[*n][0]=0;
a[*n][1]=0;
(*n)++;
}
if (str[i]=='+') a[*n][0]=5;
else a[*n][0]=6;
}
a[*n][1]=str[i];
i++;
}
(*n)++;
}
a[*n][0]=2;
a[*n][1]=')';//在表達(dá)式尾添加一個(gè)反括號(hào)
(*n)++;
}

void poland(int a[][2],int n,int p[][2],int *m)
//將格式化數(shù)組轉(zhuǎn)化為逆波蘭表達(dá)式，a為輸入的數(shù)組，n為其長(zhǎng)度，p為輸出逆波蘭表達(dá)式的目標(biāo)，m記錄逆波蘭表達(dá)式的長(zhǎng)度
{
int i;
int stack[1000];//轉(zhuǎn)化所用的棧
int depth;//棧的深度
depth=0;
*m=0;
for (i=0;i<n;i++)
{
if (a[i][0]==0) stack[depth++]=i;
else if (a[i][0]==1) stack[depth++]=i;
else if (a[i][0]==2)
{
while (a[stack[depth-1]][0]!=1)
{
depth--;
p[*m][0]=a[stack[depth]][0];
p[*m][1]=a[stack[depth]][1];
(*m)++;
}
depth--;
}
else if (a[i][0]==3 || a[i][0]==4)
{
while (a[stack[depth-1]][0]==0 || a[stack[depth-1]][0]==3 || a[stack[depth-1]][0]==4)
{
depth--;
p[*m][0]=a[stack[depth]][0];
p[*m][1]=a[stack[depth]][1];
(*m)++;
}
stack[depth++]=i;
}
else if (a[i][0]==5 || a[i][0]==6)
{
while (a[stack[depth-1]][0]!=1)
{
depth--;
p[*m][0]=a[stack[depth]][0];
p[*m][1]=a[stack[depth]][1];
(*m)++;
}
stack[depth++]=i;
}
}
}

void print_poland(int p[][2],int m)
//打印逆波蘭表達(dá)式，p為逆波蘭表達(dá)式，m為表達(dá)式長(zhǎng)度
{
int i;
for (i=0;i<m;i++)
{
if (p[i][0]==0) printf("%d",p[i][1]);
else printf("%c",p[i][1]);
}
putchar('\n');
}

double evaluate(int p[][2],int m)
//對(duì)逆波蘭表達(dá)式求值，p為逆波蘭表達(dá)式，m為表達(dá)式長(zhǎng)度
{
double stack[1000];//求值所用的棧
int depth;//棧的深度
int i;
depth=0;
for (i=0;i<m;i++)
{
if (p[i][0]==0) stack[depth++]=p[i][1];
else
{
double a,b;
b=stack[--depth];
a=stack[--depth];
if (p[i][0]==3) stack[depth++]=a*b;
else if (p[i][0]==4) stack[depth++]=a/b;
else if (p[i][0]==5) stack[depth++]=a+b;
else stack[depth++]=a-b;
}
}
return stack[0];
}

int a[1000][2];
int n;
int p[1000][2];
int m;

main()
{
transform("5*(8-2)+9",a,&n);
poland(a,n,p,&m);
print_poland(p,m);
printf("The result of the expression is %lf\n",evaluate(p,m));
return;
}