波蘭演算法

❶ （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，無意義。

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

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

❸ 逆波蘭式的演算法圖示

其中△代表一個標識，ω代表預演算法，名字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)

❹ 逆波蘭式的演算法實現

將一個普通的中序表達式轉換為逆波蘭表達式的一般演算法是：
首先需要分配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/C++演算法最好 可以執行一段指令 例如 a+b12*(c5+d24)^g12 的逆波蘭表達式 由鍵盤輸入

相當於給出中序序列 其中數字是葉子節點 然後後序遍歷樹就是逆波蘭表達式

❻ 求一個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);
}
}

❼ 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);
}