波兰算法
❶ （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);
}