java逆波蘭式演算法

㈠ java計算字元串中的數學表達式的值演算法怎麼寫

代碼網上很多，只說說演算法吧
12+8/4-5+(3-4)

把這樣的表達式拆成：(操作數)(操作符) 、
12+
8/
4-
5+(
3-
4)
(術語叫做逆波蘭式)
默認的計算順序是從左往右，記為left。另設從右往左，記為right
設計Element類，具有 操作數 operant, 操作符operator, 操作順序 order三個屬性
用兩個先進後出的棧結構Stack<Element> a,b;
一開始所有的Element都在a中，逐個彈出計算合並值，
當遇到乘、除、括弧時計算順序改變成right，把當前結果放到b中暫存。
直到再次遇到加、減、)右括弧時，意味計算順序復位成left，先把b中的暫存結果全部合並後，再繼續算a中的剩餘數據
最後合並成一個結果值。

㈡ 逆波蘭式的舉例

下面以(a+b)*c為例子進行說明：
(a+b)*c的逆波蘭式為ab+c*，假設計算機把ab+c*按從左到右的順序壓入棧中，並且按照遇到運算符就把棧頂兩個元素出棧，執行運算，得到的結果再入棧的原則來進行處理，那麼ab+c*的執行結果陸游如下：
1）a入棧（0位置）
2）b入棧（1位置）
3）遇到運算符「+」，將a和b出棧，執行a+b的操作，得到結果d=a+b，再將d入棧（0位置）
4）c入棧（1位置）
5）遇到運算符「*」，將d和c出棧，執爛悉耐行d*c的操作，得到結果e，再將e入棧（0位置）
經過以上運算，計算飢春機就可以得到(a+b)*c的運算結果e了。
逆波蘭式除了可以實現上述類型的運算，它還可以派生出許多新的演算法，數據結構，這就需要靈活運用了。逆波蘭式只是一種序列體現形式。

㈢ java 設計演算法，計算用後綴表示法表示的算術表達式的值。

你好！
後綴表達式也稱逆波蘭表達式，其優點就在於可以方便的用棧實現表達式的值的計算。和你說一下思路吧：
·從頭讀入表達式
·如果遇到數則將其壓入棧
·如果遇到運算符，從棧中彈出棧頂連個數，實行相應運算，將結果壓入棧中
·直到表達式尾，此時棧中應該只有一個元素，即運算結果
·Over
如果對你有幫助，望採納。

㈣ 如何將算術表達式轉化為逆波蘭式並求出其值

一個表核森達式E的後綴形式的定義：
（1）如果E是一個變數或常量，則E的後綴式是E自身；
（2）如果E是E1 * E2的形式(這里*代表任何二元運算)，則E的後綴式是 E'1 E'2 *，E'1和E'2分別是E1和E2的後綴表達式；
（3）如果E是（E1）形式的表達式，則E的後綴式就是E1的後綴式。

所以求逆波蘭表達嫌春式的時候與運算符的優先順序沒有關系。

具體演算法比較困難，要使用到DAG圖或者三元式，這個在編譯原理中用的比較多。

對於根據逆波蘭表達式求值就比較簡單了，用到一個棧，將字元串依次讀入棧中，遇改者畝到運算符的時候取出棧頂的兩個元素進行運算，將運算結果壓入棧中，直到將整個字元轉讀完就求出來結果了。

㈤ java如何計算比較復雜的數學計算，比如有括弧同時有+-*/，順序不一定，就是一個運算公式

可以用編譯原理的思想來理解，主要用到數據結構裡面的棧和隊列。
利用棧的後進先出以及運算符號(+-*/(){} )優先順序，對運算符號進行匹配。
分兩個棧，一個是符號棧，一個是數字棧。
棧的每一次pop出一個字元，要進行校驗，如果匹配（符合運算規則）則計算，並保存結果到數據棧。

㈥ 什麼是逆波蘭式

逆波蘭式
開放分類： c程序

逆波蘭式也叫後綴表達式(將運算符寫在操作數之後)
如：我們平時寫a+b，這是中綴表達式，寫成後綴表達式就是：ab+
(a+b)*c-(a+b)/e的後綴表達式為：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-
將一個普通的中序表達式轉換為逆裂桐波蘭表達式的一缺衡般演算法是：
1)首先構造一個運算符棧，此運算符在棧內遵循越往棧頂優先順序越高的原則。
(2)讀入一個用中綴表示的簡單算術表達式，為方便起見,設該簡單算術表達式的右端多加上了優先順序最低的特殊符號「#」。
(3)從左至右掃描該算術表達式，從第一個字元開始判斷，如果該字元是數字，則分析到該數字串的結束並將該數字串直接輸出。
(4)如果不是數字，該字元則是運算符，此時需比較優先關系。
做法如下：將該字元與運算符棧頂的運算符的優先關系相比較。如果，該字元優先關系高於此運算符棧頂的運算符，則將該運算符入棧。倘若不是的話，則將棧頂的運算符從棧中彈出，直到棧頂運算符的優先順序低於當前運算符，將該字元入棧。
(5)重復上述操作(1)-(2)直至掃描完整個簡單算術表達式，確定所有字元都得到正確處理，我們便可以將中綴式表示的簡單算術表達式轉化為逆波蘭表示的簡單算術表達式。

typedef int SElemType;

typedef struct SqStack

{ char *base;

char *top;

char stacksize;

}SqStack;

程序

void InitStack (SqStack &S)

{

S.base=(char *) malloc (STACK_INIT_SIZE *sizeof(char));

if (!S.base)

exit (OVERFLOW); //為棧S分配存儲空間失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

}

int Push(SqStack &S,char ch)

// 將元素e插入到棧S中，成為新的棧頂元素

{

if (S.top-S.base>S.stacksize) //Stack==full?

{ S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT *sizeof(char)));

if (!S.base)

{ printf(「Failure to reallocate the Memory units!:\n」);

exit(OVERFLOW);

}

S.top=S.base+S.stacksize; //To Modify pointer of Satck top

S.stacksize+=STACKINCREMENT; //To modify the size of stack

} // end of if

*S.top++=ch; //先將e送入棧頂指針所指向的單元，再將棧頂指針加1

return(OK);

} //end of Push() subfunction

int Pop(SqStack &S,char &ch)

{

if (S.top==S.base)

{

printf(「下溢！」)；

return (ERROR);

}

ch=*--S.top;

return (OK);

}

void Translation()

{//將算術表達式轉化伏源做為逆波蘭表達式，num為算術表達式的字元總個數

int i,j;

char str[100],exp[100],ch;

SqStack S;

InitStack(S);

i=1;

printf(「 請輸入算術表達式字元串，求其逆波蘭表達式，以＃為結束標志，如a-b*c/(3+6)#:\n」);

do

{

scanf(「%c」,&str);

i++;

}while(str[i-1]!=』#』);

str[0]=』(『; //將表達式放在（）內

str[i-1]=』)』;

str=』#』;

i=0;

j=0;

while(str!=』#』)

{ if((str>=』0』 &&str<=』9』)||(str>=』a』 &&str<=』z』))

{

exp[j]=str;

j++;

} //end of if

else if(str==」(」)

Push(S.str);

else if(str==』)』)

{ while(*(S.top-1)!=』(』)

//將S中左括弧「（」以前的所有字元依次彈出並存入數組exp中

{ Pop(S,ch); exp[j]=ch; j++; }

S.top--;

} //end of elseif

else if(str==』+』||str==』-』) //如果判定為「＋」號或「-」號，則做如下操作

{ while((s.top!=S.base)&&(*(S.top-1)!=』(』))

//將S中左括弧「（」以前字元依次彈出並存入數組exp 中

{ Pop(S,ch); exp[j]=ch; j++; }

Push(S,str);

} //end of else if

else if (str==』*』||str==』/』)

{

while((*(S.top-1)==』*』)||(*(S.top-1)==』/』))

{ Pop(S,ch); exp[j]=ch; j++; }

Push(S,str);

} //end of else if

i++;

} //end of while

exp[j]=』#』;

printf(「\n\n輸入的算術表達式」);

i=1;

while(str[i+1]!=』#』)

{ printf(「%c」,str);

i++;

} //end of while

printf(「 逆波蘭表達式為：\n」);

i=0;

while(exp!=』#』)

{ printf(「%c」,exp); i++; }
}
void main()
{
Translation();
printf(「\n」);
printf(「…OK…!」)
getch();
}

㈦ 逆波蘭式怎麼判斷優先順序

什麼是波蘭表達式
我們日常的運算表達式通常是如下形式，這種成為中綴表達式，也就是運算符在運算數的中間。這種表達式人類人容易識別，並根據其進行計算，但計算機識別這種表達式非常困難。
a + b * (c - d) + e/f
因此，1920年，波蘭科學家揚·武卡謝維奇（Jan ukasiewicz）發明了一種不需要括弧的計算表達式的表示法將操作符號寫在操作數之前，也就是前綴表達式，即波蘭式（Polish Notation, PN）。上述中綴表達式轉換為波蘭表達式的格式如下：
+a+*b-cd/ef
從上面表達式可以看出，運算符在2個運算數的前面，因此波蘭表達式也稱為前綴表達式。為了便於理解，我們給出一個具體的實例，這個實例將上面的字母換成具體的數字（1 + 2 * (4 - 3) + 6/2），這個結果很容易看出來，也就是1 + 2*1 + 3 = 6。然後我們看一下波蘭表達式的表示形式及運算過程。
+1+*2-4 3/ 6 2 // 從右向左掃描，當遇到運算符時計算其最近的右側2個運算數
+1+*2-4 3 3 //先計算最右側的數據，也就是 6/2=3
+1+*2 1 3 // 同理，4-3 = 1
+1+2 3 // 同理， 2*1= 1
+1+5
6
通過上面示例可以大概理解波蘭表達式的計算過程，上面的運算符和運算數就可以通過通用的數據結構進行計算（請自己思考一下，我們後面再介紹）。
什麼是逆波蘭表達式
前面了解了波蘭表達式，那什麼是逆波蘭表達式呢？波蘭表達式也成為前綴表達式，而逆波蘭表達式則成為後綴表達式，對比可以猜出來運算符在運算數後面的表達式就是逆波蘭表達式。上述表達式如果採用逆波蘭表達式則如下：
1 2 4 3 -*+ 6 2 / + //計算方式正好相反，也就是從左向右掃描
1 2 1 *+ 6 2 / +
1 2 + 6 2 / +
3 6 2 / +
3 3 +
6
從中綴表達式轉換為逆波蘭（後綴）表達式
從中綴表達式轉換為後綴表達式的流程如下描述。需要注意的是，經過處理之後，中綴表達式中的括弧將被消除，也就是只剩下+-*/數學運算符。
從左至右掃描一中綴表達式。
若讀取的是操作數，則判斷該操作數的類型，並將該操作數存入操作數堆棧
若讀取的是運算符
該運算符為左括弧"("，則直接存入運算符堆棧。
該運算符為右括弧")"，則輸出運算符堆棧中的運算符到操作數堆棧，直到遇到左括弧為止。
該運算符為非括弧運算符：
- 若運算符堆棧棧頂的運算符為括弧，則直接存入運算符堆棧。
- 若比運算符堆棧棧頂的運算符優先順序高，則直接存入運算符堆棧。
- 若比運算符堆棧棧頂的運算符優先順序低或者相等，則輸出棧頂運算符到操作數堆棧，並將當前運算符壓入運算符堆棧。
4. 當表達式讀取完成後運算符堆棧中尚有運算符時，則依序取出運算符到操作數堆棧，直到運算符堆棧為空。
將中綴表達式轉換成逆波蘭表達式過程中，特別要注意對於中綴標到式中括弧的處理。
要注意的，如果算符是"（"，無論入棧中棧頂級別（只看棧頂）為何直接入棧，所以，「(」的等級
只用於對其後入棧的算符進行優先順序比較，在「（」入棧時是無視優先順序的。
在遇到"）"時候找到最後進入的"（"，並把"（"前面所有的符號都壓入出棧。不能僅憑運算符的級別來判斷。
註： 逆波蘭用的優先順序有以下幾種， 等級從高到低分別是：
1.*
2.+ -
3.(
4.)
上面關於流程的表示文字比較多，看起悶指螞來可能比較頭疼。為了便於理解上述流程，我們依然通過上面的實例（1 + 2 * (4 - 3) + 6/2）進行介紹。在實際操作過程中需要一個棧和一個隊列，分別存儲運算符和操作數。

通螞埋過上面整個過程的描述，並結合演算法，相信大家對中綴表達式轉換為後綴表達式（波蘭表達式逗蠢）已經非常清楚了。
逆波蘭表達式的計算
逆波蘭表達式的計算就比較簡單了。以上面結果中的隊列為輸入，同時再准備一個棧用於運算。具體流程如下：
將隊列中的數據依次出隊，然後壓棧；
在出隊的過程中如果遇到運算符，則從棧中彈出2個運算數，分別作為右運算數和左運算數，進行運算；
將步驟2的運算結果入棧；
跳入步驟1，繼續進行出隊操作。
依然以上述內容為例進行介紹。
如圖1中第一行左側為形成的隊列，右側是一個空棧。將隊列中操作數依次出隊，入棧。

圖1 操作數入棧

在出隊的過程中遇到運算符（-），此時將操作數出棧進行運算（注意這里操作數的順序）。

圖2 進行運算

重復上述操作，直到將隊列中所有內容出隊。

圖3 整個運算過程

好了，今天先到這里，後續在介紹其它數據結構。