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 整个运算过程

好了，今天先到这里，后续在介绍其它数据结构。