博蘭演算法

❶ 逆波蘭式的演算法實現

將一個普通的中序表達式轉換為逆波蘭表達式的一般演算法是：
首先需要分配2個棧，一個作為臨時存儲運算符的棧S1（含一個結束符號），一個作為輸入逆波蘭式的棧S2（空棧），S1棧可先放入優先順序最低的運算符#，注意，中綴式應以此最低優先順序的運算符結束。可指定其他字元，不一定非#不可。從中綴式的左端開始取字元，逐序進行如下步驟：
（1）若取出的字元是操作數，則分析出完整的運算數，該操作數直接送入S2棧
（2）若取出的字元是運算符，則將該運算符與S1棧棧頂元素比較，如果該運算符優先順序大於S1棧棧頂運算符優先順序，則將該運算符進S1棧，否則，將S1棧的棧頂運算符彈出，送入S2棧中，直至S1棧棧頂運算符低於（不包括等於）該運算符優先順序，最後將該運算符送入S1棧。
（3）若取出的字元是「（」，則直接送入S1棧頂。
（4）若取出的字元是「）」，則將距離S1棧棧頂最近的「（」之間的運算符，逐個出棧，依次送入S2棧，此時拋棄「（」。
（5）重復上面的1~4步，直至處理完所有的輸入字元
（6）若取出的字元是「#」，則將S1棧內所有運算符（不包括「#」），逐個出棧，依次送入S2棧。
完成以上步驟，S2棧便為逆波蘭式輸出結果。不過S2應做一下逆序處理。便可以按照逆波蘭式的計算方法計算了！

❷ C語言編寫逆波蘭計算器

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.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);
}

❸ C語言 逆波蘭表達式 演算法

#include <stdio.h>
#include <string.h>

int main()
{
double d[100], *dp = d;
int m, k;
char t[50], *tp = t;
char s[100], *c = s;
char* op = "+-*/";
char* fg = "0123456789.";

gets(s);

while(*c) {
if(strchr(op, *c)) {
*tp++ = *c;
k = 0;
}else
if(strchr(fg, *c)) {
sscanf(c, "%lf%n", dp++, &m);
c += m - 1;
++k;
}
++c;
while((dp - d > 1 && k == 2) || !*c && dp - d >= 1) {
switch(*--tp) {
case '+': dp[-2] = dp[-2] + dp[-1]; break;
case '-': dp[-2] = dp[-2] - dp[-1]; break;
case '*': dp[-2] = dp[-2] * dp[-1]; break;
case '/': dp[-2] = dp[-2] / dp[-1]; break;
}
--dp;
}
}
printf("%f", *dp);
}

❹ （C語言中）逆波蘭演算法（及計算器）

逆波蘭式子又叫做後綴表達式。（相對於前綴和中綴，但是它倆都破壞了式子本身，所以用後綴）

12+3應該表達為12 3+。（實際無空格，為了好看）
先解決一個問題，就是123+會不會認為是1和23或者1和2和3，其實是不會的。一般後綴式都是用棧存儲的，你在定義棧的時候裡面的elemtype e（當然也可以用別的就是舉例），這個elemtype是重命名的int。scanf或者cin輸入的時候，你先輸入12，這個就被存在棧的第一空裡面（因為是%d嘛），再輸入3就被存在第二空裡面了。這個不會混淆。

逆波蘭演算法是這么工作的：在後綴式中掃描，可能會掃描到一堆數字，但是這時候如果掃描到了一個運算符（加減乘除等），這時候提取運算符並提取運算符前面緊挨著的那兩個數字（注意是緊挨），然後這兩個數字和這一個運算符進行運算。比如123+，掃描得12，掃描得3，掃描得+（電腦得到了+這個運算符），緊接著取前面緊挨的12和3,進行運算，就是12+3了。如(2+1) * 3就是21+3*。掃描得2，掃描得1，掃描得+，ok這時候2+1=3,3入棧，重新while掃描。掃描得3（剛才算出來剛入棧的那個），掃描得3，掃描得*，ok這時候3*3=9。

1+23這種後綴式是表達不出來的。後綴它的意義就在於兩個數，他們的運算符關系緊挨在他們後面。這個1+只有一個數，還原算是就是+1，無意義。

❺ 逆波蘭式的演算法圖示

其中△代表一個標識，ω代表預演算法，名字Q代表變數（如int a，b等），
演算法用到三個棧：a棧，b棧，in棧。
其中a棧用來存儲逆波蘭式，b用來存儲△號和運算符，in棧為輸入棧。
第一豎排為b棧中符號，第一橫排為輸入棧中符號。
pop（in）為輸入棧棧頂元素出棧，pop（a，Q）為Q入a棧，NEXT演算法即為進行下一輪循環，其中ω1<ω2為算符優先順序，如「+」和「-」<「*」和「/」。pop（b，B），push（b，B）中B為臨時變數，用來存儲出棧的元素。stop為演算法結束。
演算法開始時，現將△如b棧，輸入棧以#號結尾。
? 輸入流
b[s-1] 名字Q? ( ω2 )? # △ POP(in);
PUSH(a，Q)
NEXT POP(in);
PUSH(b，△)
NEXT POP(in)
PUSH(b，ω2)
NEXT POP(in)
POP(b，B)?NEXT STOP ω1 POP(in)
PUSH(a，Q)?
NEXT POP(in)
PUSH(b，△)
NEXT 若ω1<ω2，則
POP(in)
PUSH(b，ω2)
NEXT?
若ω1≥ω2，則POP(in)
POP(b，B），
PUSH(a,B) POP(b，B)
PUSH(a，B) POP(b，B)
PUSH(a，B)

❻ 請教波蘭表達式前綴表達式的演算法

對於一個前綴表達式的求值而言，首先要從右至左掃描表達式，從右邊第一個字元開始判斷，如果當前字元是數字則一直到數字串的末尾再記錄下來，如果是運算符，則將右邊離得最近的兩個「數字串」作相應的運算，以此作為一個新的「數字串」並記錄下來。一直掃描到表達式的最左端時，最後運算的值也就是表達式的值。例如，前綴表達式「- 1 + 2 3「的求值，掃描到3時，記錄下這個數字串，掃描到2時，記錄下這個數字串，當掃描到+時，將+右移做相鄰兩數字串的運算符，記為2+3，結果為5，記錄下這個新數字串，並繼續向左掃描，掃描到1時，記錄下這個數字串，掃描到-時，將-右移做相鄰兩數字串的運算符，記為1-5，結果為-4，所以表達式的值為-4。