字首表達式,是一種對計算機來言特别好處理的表達式,為什麼？
以下為計算機自己的表達 請自行編譯：
#include<bits/stdc++.h>
using namespace std;
int main()
{
<span style="white-space:pre"> </span>cout<<"因為我本身就是隻會處理字首表達式,中綴表達式對我來言很複雜,往往要處理成字首表達式才行！！！";
}
聽到這裡你估計會神馬!!!,沒錯其實計算機本身就是以"字首表達式"處理的.什麼是中綴？先賣個關子,那麼字首表達式怎麼使用？請看下節分曉！！！
規則如下所示:
對字首表達式求值，要從右至左掃描表達式，首先從右邊第一個字元開始判斷，若目前字元是數字則一直到數字串的末尾再記錄下來，若為運算符，則将右邊離得最近的兩個“數字串”作相應運算，然後以此作為一個新的“數字串”并記錄下來；掃描到表達式最左端時掃描結束，最後運算的值即為表達式的值。 例如：對字首表達式“- 1 + 2 3”求值，掃描到3時，記錄下這個數字串，掃描到2時，記錄下這個數字串，當掃描到+時，将+右移做相鄰兩數字串的運算符，記為2+3，結果為5，記錄下5這個新數字串，然後繼續向左掃描，掃描到1時，記錄下這個數字串，掃描到-時，将-右移做相鄰兩數字串的運算符，記為1-5，結果為-4，此時關于這個表達式的全部運算已完成，故表達式的值為-4。 以上借鑒百度大佛！！！(阿彌陀佛！善哉善哉........以下省略9億個字
) 比如說17屆NOIP初賽的選擇題第九題： 字首表達式:+3*2+5 12的值 A:23 B:25 C:37 D:65 答案：C
解析：這道題目化成中綴就是:(3+2)*5+12.怎麼化呢.休息一下馬上回來。估計你會這樣
！！！好了
言歸正傳.剛開始是+号入棧,然後找到兩個和他最近的的數字元.那就是3和2,于是原式=3+2*+5 12.(又回到當年的數學模式呵呵),繼續開工,報告發現*,嗯不錯，綁架5和12,是！哇還發現+,他比*小，先上， 于是原式=(3+2)*(5+12)，為什麼加括号,你懂的孩紙,因為這就是大名鼎鼎中綴表達式.好深奧.等等,這不就是我們日常用的四則運算大法.你估計會(好吧,原來他就是中綴表達式.原來是這樣,我還以為是多麼高檔次的東西,不開森
),好了好歹學會了兩種表達式.那麼如何轉換？？？
阿彌陀佛,百度大僧來了
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 99
char calc[MaxSize],expr[MaxSize];
int i,t;
struct
{
char data[MaxSize];
int top;
}Sym;
struct
{
double data[MaxSize];
int top;
}Num;
double ston(char x[],int *p)
{
int j=*p-1,i;
double n=0,m=0;
while(x[j]>='0'&&x[j]<='9')
{
j--;
}
if(x[j]!='.')
{
for(i=j+1;i<=*p;i++)
{
n=10*n+(x[i]-'0');
}
}
else
{
for(i=j+1;i<=*p;i++)
{
m=m+pow(0.1,i-j)*(x[i]-'0');
}
if(x[j]=='.')
{
*p=--j;
while(x[j]>='0'&&x[j]<='9')
{
j--;
}
for(i=j+1;i<=*p;i++)
{
n=10*n+(x[i]-'0');
}
}
}
*p=j;
if(x[*p]=='-') return(-(n+m));
return(n+m);
}
void InitStack()
{
Sym.top=Num.top=-1;
}
void SymPush()
{
if(Sym.top<MaxSize-1)
{
Sym.data[++Sym.top]=calc[i--];
}
else
{
printf("Sym棧滿\n");
return;
}
}
void SymPop()
{
if(Sym.top>=0)
{
expr[++t]=Sym.data[Sym.top--];
}
else
{
printf("Sym棧空\n");
return;
}
}
void NumPush()
{
if(Num.top<MaxSize-1)
{
Num.data[++Num.top]=ston(expr,&i);
}
else
{
printf("Num棧滿\n");
return;
}
}
void NumPop()
{
if(Num.top>=0)
{
if(expr[i]!=' ')
{
switch(expr[i])
{
case '+':Num.data[Num.top-1]=Num.data[Num.top]+Num.data[Num.top-1];break;
case '-':Num.data[Num.top-1]=Num.data[Num.top]-Num.data[Num.top-1];break;
case '*':Num.data[Num.top-1]=Num.data[Num.top]*Num.data[Num.top-1];break;
case '/':Num.data[Num.top-1]=Num.data[Num.top]/Num.data[Num.top-1];break;
case '^':Num.data[Num.top-1]=pow(Num.data[Num.top],Num.data[Num.top-1]);break;
}
Num.top--;
}
}
else
{
printf("Num棧空\n");
return;
}
}
int main(void)
{
char ch;
loop1:
i=0,t=-1;
//system("cls");
printf("中綴表達式：");
InitStack(),gets(calc);
while(calc[i]!='\0')
{
i++;
}
while(i>=0)
{
if(calc[i]>='0'&&calc[i]<='9')
{
while((i>=0)&&((calc[i]>='0'&&calc[i]<='9')||(calc[i]=='.')))
{
loop2:
expr[++t]=calc[i--];
}
if((i>=0)&&((i==0&&calc[i]!='(')||(calc[i]=='+'||calc[i]=='-')&&!(calc[i-1]>='0'&&calc[i-1]<='9')&&calc[i-1]!=')')) goto loop2;
expr[++t]=' ';
}
else if(calc[i]==')')
{
SymPush();
}
else if(calc[i]=='(')
{
while(Sym.data[Sym.top]!=')')
{
SymPop();
expr[++t]=' ';
}
Sym.data[Sym.top--]='\0';
i--;
}
else if(calc[i]=='+'||calc[i]=='-')
{
while(Sym.top>=0&&Sym.data[Sym.top]!=')'&&Sym.data[Sym.top]!='+'&&Sym.data[Sym.top]!='-')
{
SymPop();
expr[++t]=' ';
}
SymPush();
}
else if(calc[i]=='*'||calc[i]=='/')
{
while(Sym.top>=0&&Sym.data[Sym.top]=='^')
{
SymPop();
expr[++t]=' ';
}
SymPush();
}
else if(calc[i]=='^')
{
SymPush();
}
else
{
i--;
}
}
while(Sym.top>=0)
{
SymPop();
expr[++t]=' ';
}
expr[++t]=Sym.data[++Sym.top]='\0';
for(i=0;i<=(t-2)/2;i++)
{
ch=expr[i];
expr[i]=expr[(t-2)-i];
expr[(t-2)-i]=ch;
}
printf("字首表達式：%s\n",expr);
for(i=t-2;i>=0;i--)
{
if((expr[i]>='0'&&expr[i]<='9')||((expr[i]=='+'||expr[i]=='-')&&(expr[i+1]>='0'&&expr[i+1]<='9')))
{
NumPush();
}
else
{
NumPop();
}
}
printf("運算結果為：%g\n",Num.data[0]);
printf("Continue(y/n)?");
ch=getchar();
switch(ch)
{
case 'y':{;goto loop1;}
case 'n':
default :exit(0);
}
getchar();
return(0);
}