逆波蘭演算法
⑴ 如何將算術表達式轉化為逆波蘭式並求出其值
一個表達式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逆波蘭演算法的代碼,要帶輸入框.就是可以根據輸入框的內容用逆波蘭演算法求出答案.
已發送。多加點分哈
import java.awt.Button;
import java.awt.FlowLayout;
import java.awt.Label;
import java.awt.TextField;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;
//棧類
class Stacks {
private LinkedList list = new LinkedList();
int top = -1;
public void push(Object value) {
top++;
list.addFirst(value);
}
public Object pop() {
Object temp = list.getFirst();
top--;
list.removeFirst();
return temp;
}
public Object top() {
return list.getFirst();
}
}
class Expression {
private ArrayList expression = new ArrayList();// 存儲中序表達式
private ArrayList right = new ArrayList();// 存儲右序表達式
private String result;// 結果
// 依據輸入信息創建對象，將數值與操作符放入ArrayList中
Expression(String input) {
StringTokenizer st = new StringTokenizer(input, "+-*/()", true);
while (st.hasMoreElements()) {
String s = st.nextToken();
expression.add(s);
}
}
// 將中序表達式轉換為右序表達式
private void toRight() {
Stacks aStack = new Stacks();
String operator;
int position = 0;
while (true) {
if (Calculate.isOperator((String) expression.get(position))) {
if (aStack.top == -1
|| ((String) expression.get(position)).equals("(")) {
aStack.push(expression.get(position));
} else {
if (((String) expression.get(position)).equals(")")) {
while (true) {
if (aStack.top != -1
&& !((String) aStack.top()).equals("(")) {
operator = (String) aStack.pop();
right.add(operator);
} else {
if (aStack.top != -1)
aStack.pop();
break;
}
}
} else {
while (true) {
if (aStack.top != -1
&& Calculate.priority((String) expression
.get(position)) <= Calculate
.priority((String) aStack.top())) {
operator = (String) aStack.pop();
if (!operator.equals("("))
right.add(operator);
} else {
break;
}
}
aStack.push(expression.get(position));
}
}
} else
right.add(expression.get(position));
position++;
if (position >= expression.size())
break;
}
while (aStack.top != -1) {
operator = (String) aStack.pop();
if (!operator.equals("("))
right.add(operator);
}
}
// 對右序表達式進行求值
String getResult() {
String str = "";
this.toRight();
for (int i = 0; i < right.size(); i++) {
System.out.println(right.get(i));
}
Stacks aStack = new Stacks();
String op1, op2, is = null;
Iterator it = right.iterator();
while (it.hasNext()) {
is = (String) it.next();
if (Calculate.isOperator(is)) {
op1 = (String) aStack.pop();
op2 = (String) aStack.pop();
aStack.push(Calculate.twoResult(is, op1, op2));
} else
aStack.push(is);
}
result = (String) aStack.pop();
it = expression.iterator();
while (it.hasNext()) {
str += (String) it.next();
}
str += "\n=" + result;
return str;
}
}
class Calculate {
// 判斷是否為操作符號
public static boolean isOperator(String operator) {
if (operator.equals("+") || operator.equals("-")
|| operator.equals("*") || operator.equals("/")
|| operator.equals("(") || operator.equals(")"))
return true;
else
return false;
}
// 設置操作符號的優先順序別
public static int priority(String operator) {
if (operator.equals("+") || operator.equals("-"))
return 1;
else if (operator.equals("*") || operator.equals("/"))
return 2;
else
return 0;
}
// 做2值之間的計算
public static String twoResult(String operator, String a, String b) {
try {
String op = operator;
String rs = new String();
double x = Double.parseDouble(b);
double y = Double.parseDouble(a);
double z = 0;
if (op.equals("+"))
z = x + y;
else if (op.equals("-"))
z = x - y;
else if (op.equals("*"))
z = x * y;
else if (op.equals("/"))
z = x / y;
else
z = 0;
return rs + z;
} catch (NumberFormatException e) {
System.out.println("input has something wrong!");
return "Error";
}
}
}
public class Test extends JFrame {
JTextField exprss;
JLabel rlt;
JButton button;
public Test() {
this.setSize(500, 200);// 設置大小
this.setTitle("第一個JFrame的窗體!"); // 設置標題處的文字
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);// 窗體關閉時的操作 退出程序
double width = Toolkit.getDefaultToolkit().getScreenSize().width; // 得到當前屏幕解析度的高
double height = Toolkit.getDefaultToolkit().getScreenSize().height;// 得到當前屏幕解析度的寬
this.setLocation((int) (width - this.getWidth()) / 2,
(int) (height - this.getHeight()) / 2); // 設置窗體居中顯示
this.setResizable(false);// 禁用最大化按鈕
JPanel contentPane = (JPanel) this.getContentPane();
contentPane.setLayout(new FlowLayout());
exprss = new JTextField(10);
rlt = new JLabel();
rlt.setSize(200, 20);
button = new JButton("計算");
contentPane.add(exprss);
contentPane.add(button);
contentPane.add(rlt);
button.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
try {
String input = exprss.getText().trim();
Expression boya = new Expression(input);
String str = boya.getResult();
rlt.setText(str);
} catch (Exception ex) {
rlt.setText("Wrong input!!!");
}
}
});
}
public static void main(String avg[]) {
Test test = new Test();
test.setVisible(true);
}
}
⑶ 逆波蘭式的演算法實現
將一個普通的中序表達式轉換為逆波蘭表達式的一般演算法是：
首先需要分配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程序
逆波蘭式也叫後綴表達式(將運算符寫在操作數之後)
如：我們平時寫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();
}
⑸ 逆波蘭式的演算法圖示
其中△代表一個標識，ω代表預演算法，名字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)
⑹ 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);
}
⑺ 數學表達式轉換成後綴式(逆波蘭式),對後綴式進行計算,
中綴表達式如1*2+(2-1), 其運算符一般出現在操作數之間, 因此稱為中綴表達式,也就是大家編程中寫的表達式。編譯系統不考慮表達式的優先順序別, 只是對表達式從左到右進行掃描, 當遇到運算符時, 就把其前面的兩個操作數取出, 進行操作。為達到上述目的, 就要將中綴表達式進行改寫,變為後綴表達式 如上面的表達式
1*2+(2-1), 就變為12*21-+;
後綴表達式中不含有括弧, 且後綴表達式的操作數和中綴表達式的操作數排列次序完全相同, 只是運算符的次序發生了改變。我們實現的時候，只需要用一個特定工作方式的數據結構（棧），就可以實現。
其中stack op;用來存放運算符棧。數組ans用來存放後綴表達式。
演算法思想：
從左到右掃描中綴表達式，是操作數就放進數組ans的末尾。
如果是運算符的話，分為下面3種情況：
1）如果是『（』直接壓入op棧。
2）如果是『）』，依次從op棧彈出運算符加到數組ans的末尾，知道遇到'（'；
3) 如果是非括弧，比較掃描到的運算符，和op棧頂的運算符。如果掃描到的運算符優先順序高於棧頂運算符
則，把運算符壓入棧。否則的話，就依次把棧中運算符彈出加到數組ans的末尾，直到遇到優先順序低於掃描
到的運算符，並且把掃描到的運算符壓入棧中。
就這樣依次掃描，知道結束為止。
如果掃描結束，棧中還有元素，則依次彈出加到數組ans的末尾，就得到了後綴表達式。
我空間裡面有詳細介紹，中綴轉換後綴的代碼和問題描述，主要是理解演算法的思想，和數據結構，這樣才算掌握了。
http://hi..com/huifeng00/blog/item/70cb280dabd9d4216059f3d1.html