逆波兰算法

⑴ 如何将算术表达式转化为逆波兰式并求出其值

一个表达式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