本文目錄一覽：
- 1、C語言 逆波蘭表達式
- 2、逆波蘭表達式求值 c++
- 3、C語言編寫逆波蘭計算器
- 4、逆波蘭表達式（遞歸）形成棧
- 5、C語言求解逆波蘭表達式
- 6、C語言逆波蘭算數表達式
C語言 逆波蘭表達式
這個問題可以分為3部分
1、輸入一個字元串，將其格式化的儲存在一個數組中，以方便的記錄表達式中數和各個符號的出現順序
約定在數組中記錄時，每個數或符號用兩個整數來記錄
第一個整數記錄該位是什麼東西，0表示是一個數，1表示是括弧，2表示反括弧，3、4、5、6分別表示乘除加減號
如果該位是一個數，那麼第二個整數記錄著個數的具體取值，否則記錄該位的符號的ASCII碼
比如字元串”(1-23)”會被轉化成二位數組 , , , , }
這個轉化過程每什麼技巧性，對原字元串各位順次判斷並處理即可
原先的字元串中可能出現一元運算符正號’+’和負號’-‘，為了處理方便，一律在其前面加個0，改寫成”0+…”或者”0-…”
另外為了之後轉化逆波蘭表達式方便，處理過程中會在轉化出的數組的首尾一律添加一對括弧
2、將之前所提到的格式數組轉化為逆波蘭表達式
約定依然用二位數組記錄一個逆波蘭表達式，並且格式與之前的數組相同，除了沒有括弧以外
比如逆波蘭表達式 1 2 – 35 +，會被記錄成{ , , , , }
轉化時，需要用一個棧
具體轉化操作如下：
順次處理格式數組的每一位，對其作判斷
如果該位是一個數或者是括弧'(‘，，將其入棧
如果該位是乘號’*’或者除號’/’，不斷進行出棧操作直到棧頂元素是個括弧'(‘或者加號’+’或者減號’-‘，然後將這個乘號或者除號入棧
如果該位是加號’+’或者減號’-‘，不斷進行出棧操作直到棧頂元素是個括弧'(‘，然後將這個加號或者減號入棧
如果該位是反括弧’)’，那麼不斷進行出棧操作直到有一個括弧'(‘出棧
在上述操作中，所有的出棧元素，除了括弧'(‘以外，都被順次添加到所要生成的逆波蘭表達式的末尾
這樣就轉化出了一條逆波蘭表達式
3、對逆波蘭表達式求值
求值時，也需要用到一個棧
求值步驟如下：
順次處理逆波蘭表達式的每一位，對其作判斷
如果該位是一個數，將這個數入棧
如果該位是一個運算符，那麼連續進行兩次出棧操作，可以得到棧頂的兩個元素，對這兩個元素用該位的運算符做運算，將所得的結果入棧
比如，如果當時棧頂元素是3，次棧頂的元素是2，運算符是減號’-‘，那麼連續兩次出棧得到3和2兩個元素，再將2-3的運算結果1入棧
注意有些運算符(減號和除號)不符合交換律，因此運算時必須是次棧頂元素在前、棧頂元素在後，順序不能反
當每一位都處理完了之後，只要輸入的是一個合法的逆波蘭表達式，必然棧中只剩下一個元素，這個元素就是逆波蘭表達式求值的結果
源代碼如下：
#include stdio.h
#include ctype.h
void transform(char *str,int a[][2],int *n)
//將輸入的字元串轉化為格式化的數組以記錄輸入的表達式，str為輸入的字元串，a為目標數組，n記錄數組a的大小
{
int i;
*n=1;
a[0][0]=1;
a[0][1]='(‘;//在表達式首添加一個括弧
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]=’)’;//在表達式尾添加一個反括弧
(*n)++;
}
void poland(int a[][2],int n,int p[][2],int *m)
//將格式化數組轉化為逆波蘭表達式，a為輸入的數組，n為其長度，p為輸出逆波蘭表達式的目標，m記錄逆波蘭表達式的長度
{
int i;
int stack[1000];//轉化所用的棧
int depth;//棧的深度
depth=0;
*m=0;
for (i=0;in;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)
//列印逆波蘭表達式，p為逆波蘭表達式，m為表達式長度
{
int i;
for (i=0;im;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)
//對逆波蘭表達式求值，p為逆波蘭表達式，m為表達式長度
{
double stack[1000];//求值所用的棧
int depth;//棧的深度
int i;
depth=0;
for (i=0;im;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;
}
逆波蘭表達式求值 c++
這是典型的遞歸演算法（這是前綴表達式吧）即在函數中調用函數本身第一層遞歸時接受輸入字元（緩衝區10字元，第一個字元默認為0，防止不輸入）並讀取第一個字元。（總的來說就是為了讀取單個運算符號或者一串數字列）若讀取出為運算符號如’+’則在return時調用f()+f()這裡有兩次調用f()，每次調用f()時都需要請求你輸入字元。這兩次調用f()時，即進入了第二層遞歸。假定這裡你兩次輸入了’1′,’2’那麼對於第一層遞歸中的returnf()+f();其中第一個f()中返回了你的輸入1，第二個則返回2此時回到第一層，在f()+f()時就運算出結果3最終退出第一層遞歸，回到main()輸出前綴表達式的結果。如果更加複雜（輸入了很多運算符），同樣可以按照上面所說的這種思想來看。關於遞歸，一開始理解起來會有些困難，可以找些例子並且自己試驗。
C語言編寫逆波蘭計算器
#includestdio.h
#includestdbool.h
#includestdlib.h
#defineSTACK_SIZE 20
intmake_empty(void);
boolis_empty(void);
boolis_full(void);
voidpush(char );
voidpop(char );
voidstack_overflow(void);
voidstack_underflow(void);
charcontents[STACK_SIZE]= {0},top;
intmain(int argc, char *argv[])
{
char ch=’1′;
while(ch!=’q’){
make_empty();
printf(“Enter an RPNexpression:”);
do{
scanf(” %c”,ch);
if(ch=’1’ch=’9′)
push(ch);
else if(ch==’+’||ch==’-‘||ch==’*’||ch==’/’){
top–;pop(ch);
}
else if(ch==’=’){
if((top-1)==0)
pop(ch);
else
printf(“Nunber notused!”);
break;
}
else if(ch==’\n’);
else{
ch=’q’;break; /*其它情況置為退出標誌q*/
}
}
while(ch!=’\n’);
}
return 0;
}
intmake_empty(void){
/* return top=0;
}
boolis_empty(void){
return top==0;
}
boolis_full(void){
return top==STACK_SIZE;
}
voidpush(char ch){
if(is_full())
stack_overflow();
else
contents[top++]=ch-‘0’;
}
voidpop(char ch){
if(is_empty())
stack_underflow();
else
switch(ch){
case’+’:contents[top-1]+=contents[top];break;
case ‘-‘:contents[top-1]-=contents[top];break;
case’*’:contents[top-1]*=contents[top];break;
case’/’:contents[top-1]/=contents[top];break;
case ‘=’:printf(“Value ofexpression:%d\n”,(int)contents[0]);break;
}
}
voidstack_overflow(void){
printf(“Expression is toocomplex!”);
exit(EXIT_FAILURE);
}
voidstack_underflow(void){
printf(“Not enough operands inexpression!”);
exit(EXIT_FAILURE);
}
逆波蘭表達式（遞歸）形成棧
不是，cin只是用來讀取數據。
實際上這個程序巧妙地用了遞歸（底層原理是系統棧，有65000層）代替數據結構的棧，使程序代碼更加簡潔（但是在運算符超過65000個時系統棧可能會「爆棧」）。
C語言求解逆波蘭表達式
使用棧完成
int add(char s[])
{
int st[100];
char *p;
int top=-1;
int A,B,sum=0;
for(p=s;*p!=0;p++)//進行數值計算
{
switch (*p)
{
case ‘0’:
case ‘1’:
case ‘2’:
case ‘3’:
case ‘4’:
case ‘5’:
case ‘6’:
case ‘7’:
case ‘8’:
case ‘9’:st[++top]=*p-‘0’;break;//是數字壓入總棧st中
case ‘+’:
case ‘-‘:
case ‘*’:
case ‘/’://是運算符號
A=st[top–];
B=st[top–];//彈出2個數字
switch (*p)
{
case ‘+’:sum=B+A;break;
case ‘-‘:sum=B-A;break;
case ‘*’:sum=B*A;break;
case ‘/’: sum=B/A;break;
}
st[++top]=sum;//將結果重新壓入棧
break;
}
}
return sum;
}
C語言逆波蘭算數表達式
我用c語言寫的wintc下運行正確 希望對你有幫助
#includestdio.h
#includestring.h
int nibolan(char s[])
{ int i=0,a,b;
char *p;
p=s ;
while(*p!=’\0′)
{if(*p==’+’){*p=((*(p-2)-48)+(*(p-1)-48))+48;}
if(*p==’-‘){*p=((*(p-2)-48)-(*(p-1)-48))+48;}
if(*p==’*’){*p=((*(p-2)-48)*(*(p-1)-48))+48;}
if(*p==’/’){*p=((*(p-2)-48)/(*(p-1)-48))+48;}
p++;
} p–;
return (*p)-48;
}
main()
{ int r;
char a[100];
gets(a);
r=nibolan(a);
printf(“%d”,r);
getch();
}
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/293189.html
微信掃一掃 
支付寶掃一掃 