1. java解析字元串 算術表達式求值
Java 有一個jar包 叫groovy
groovy可以實現動態執行 String格式的算數表達式
publicstaticvoidmain(String[]args)throwsException{
Stringstr1="1+2*3";//表達式1固定表達式
GroovyShellgroovyShell=newGroovyShell();
Objectvalue=groovyShell.evaluate(str1);
System.out.println(value);
Stringstr2="A+B*C";//表達式2動態表達式
Bindingbinding=newBinding();
binding.setVariable("A",1);//表達式中所有的A替換為1
binding.setVariable("B",2);//表達式中所有的B替換為2
binding.setVariable("C",3);//表達式中所有的C替換為3
GroovyShellgroovyShell2=newGroovyShell(binding);
Objectvalue2=groovyShell2.evaluate(str2);//str2實際表達式為1+2*3
System.out.println(value2);
}
2. java表達式是什麼
Java是面向表達式的語言，Java中一個簡單表達式可以是下面任意一種：● 常量：7、false。● 單引號括起來的字元字面常量：'A'、'3'。● 雙引號括起來的字元串字面常量："foo"、"Java"。● 任何正確聲明的變數名：myString、x。● 任何用Java二元運算符（本章稍後將詳細討論）連接起來的兩個上述類型的表達式：x+2。● 任何用Java一元運算符（本章稍後將詳細討論）修飾的單個上述類型的表達式：i++。● 任何用小括弧括起來的上述類型的表達式：(x+2)。以及另外一些與本書後面將要學到的對象有關的表達式類型。無論多麼復雜的表達式都可以由不同類型的簡單表達式和括弧嵌套組合而成，例如：((((4/x) + y) * 7) + z)。2.9.1 算術運算符 Java語言提供了許多基本的算術運算符，如表2-1所示。表2-1 Java算術運算符運算符描 述+加法-減法*乘法/除法%求余（%左邊的操作數除以右邊的
操作數所得到的余數，例如10%3=1）+和-運算符也可作為一元運算符用於表示正負數：-3.7、+42。除了簡單賦值運算符=，還有許多特定的復合賦值運算符，這些運算符將變數賦值和算術操作合並在一起，如表2-2所示。表2-2 Java復合賦值運算符運算符描 述+=a+=b等價於a=a+b-=a-=b等價於a=a-b*=a*=b等價於a=a*b/=a/=b等價於a=a/b%=a%=b等價於a=a%b最後要介紹的兩個算術運算符是一元遞增運算符（++）和一元遞減運算符（--），用於將整數變數的值加1或減1，或者將浮點數變數的值加1.0或減1.0。稱它們為一元運算符是因為它們用於單個變數，而前面討論的二元運算符則連接兩個表達式的值。一元遞增運算符和一元遞減運算符也可用於將字元變數在Unicode序列中向前或向後移動一個字元位置。例如，在下面的代碼片段中，字元變數c的值從'e'遞增為'f'：遞增和遞減運算符可以以前綴或者後綴方式使用。如果運算符放在操作數之前（前綴模式），變數的遞增或遞減操作將在更新後的變數值被用於任何由它構成的賦值操作之前執行。例如，考慮下面的使用前綴遞增運算符的代碼片段，假設a和b在程序前面已經聲明為int變數：上述代碼執行後，變數a的值是2，變數b的值也是2。這是因為在第二行中變數a的遞增（從1到2）發生在它的值賦給b之前。因此這行代碼在邏輯上等價於下面兩行代碼： 另一方面，如果運算符放在操作數之後（後綴模式），遞增或遞減操作發生在原來的變數值被用於任何由它構成的賦值操作之後。看一下以後綴方式使用遞增運算符的相同代碼片段：上述代碼執行後，變數b的值是1，而變數a的值是2。這是因為在第二行中變數a的遞增（從1到2）發生在它的值賦給b之後。因此這行代碼在邏輯上等價於下面兩行代碼：下面是一個稍微復雜一點例子，請閱讀附加的注釋以確保你能夠明白x最終是如何被賦值為10的：稍後將會看到，遞增和遞減運算符通常和循環一起使用。2.9.2 關系和邏輯運算符邏輯表達式以指定的方式比較兩個（簡單或者復雜）表達式exp1和exp2，決議出一個boolean值true或者false。 Java提供了表2-3所示的關系運算符來創建邏輯表達式。表2-3 Java關系運算符運算符描 述exp1==exp2如果exp1等於exp2，值為true（注意使用雙等號測試相等性）exp1>exp2如果exp1大於exp2，值為trueexp1>=exp2如果exp1大於等於exp2，值為trueexp1<exp2如果exp1小於exp2，值為trueexp1<=exp2如果exp1小於等於exp2，值為trueexp1!=exp2如果exp1不等於exp2，值為true!exp如果exp為false值為true，如果exp為true值為false除了關系運算符，Java還提供了用於組合/修飾邏輯表達式的邏輯運算符。表2-4列出了最常用的邏輯運算符。表2-4 Java邏輯運算符運算符描 述exp1&&exp2邏輯「與」，僅當exp1和exp2都為true時復合表達式值為trueexp1||exp2邏輯「或」，exp1或exp2值為true時復合表達式值為true!exp邏輯「非」，將邏輯表達式的值從true切換到false，反之亦然下面這個例子用邏輯「與」運算符來編程實現邏輯表達式「如果x大於2.0且y不等於4.0」：邏輯表達式常用於流程式控制制結構，本章稍後將進行討論。2.9.3 表達式求值和運算符優先順序如同本章前面提到的那樣，任何復雜的表達式都可以用分層嵌套的小括弧構成，例如(((8 * (y + z)) + y) x)。編譯器通常按照從內到外，從左到右的順序對這樣的表達式求值。假設x、y、z按照下面的方式聲明並初始化：下面的賦值語句右邊的表達式：將像下面這樣逐步求值：沒有小括弧時，根據運算符用於表達式求值的順序，某些運算符具有高於其他運算符的優先順序。例如，乘除法先於加減法執行。通過使用小括弧可以強制改變運算符的優先順序，括弧內的運算符比括弧外的先執行。考慮下面的代碼片段：代碼的第一行沒有使用括弧，乘法操作比加法操作先執行，因此整個表達式的值為2+12=14，就像我們將表達式明確地寫成2+(3*4)一樣，當然這樣做沒有必要。 在代碼的第二行，括弧被明確地放在操作2+3兩邊，因此加法操作將首先執行，然後求和結果乘以4作為整個表達式的值，即5*4=20。回到前面的例子注意到>和!=運算符優先順序高於&&運算符，因此可以去掉嵌套的括弧而變成下面這樣：然而，額外的括弧並不會對代碼造成傷害，事實上它可以使表達式的目的更加清楚。2.9.4 表達式類型表達式類型是表達式最終求值結果的Java類型。例如給定下面的代碼片段：表達式(x > 2.0) && (y != 4.0)求值結果為true，因此表達式(x > 2.0) && (y != 4.0)稱為boolean型表達式。在下面的代碼片段中：表達式((8 * (y + z)) + y) * x求值結果為42，因此表達式((8 * (y + z)) + y) * x稱為整型表達式。
3. java 如何對String類型的邏輯表達式求值
對String類型的邏輯表達式求值
import java.util.ArrayList;
import java.util.Stack;
/**
*
* @author yhh
*
*/
public class Calculate {
/**
* 將字元串轉化成List
* @param str
* @return
*/
4. 表達式求值 數據結構 java實現
1. 定義優先順序和優先順序表
Java代碼
/**
* 運算符優先權
*/
public enum Precede {
/**
* 優先權高
*/
LARGER,
/**
* 優先權低
*/
LESS;
/**
* 優先順序表
* + - * /
* + > > < <
* - > > < <
* * > > > >
* / > > > >
*/
private static Precede[][] precedes = new Precede[4][4];
static {
// 根據優先順序表初始化precedes數組
for (int i = 0; i < precedes.length; i++) {
for (int j = 0; j < precedes[i].length; j++) {
if ((i == 0 || i == 1) && j > 1) {
precedes[i][j] = LESS;
} else {
precedes[i][j] = LARGER;
}
}
}
}
/**
* 判斷2個運算符的優先順序
*/
public static Precede judgePrecede(char operand1, char operand2) {
int left = getIndex(operand1);
int right = getIndex(operand2);
return precedes[left][right];
}
/**
* 獲取運算符對應的數組索引
*/
private static int getIndex(char operand) {
switch (operand) {
case '+':
return 0;
case '-':
return 1;
case '*':
return 2;
case '/':
return 3;
default:
throw new IllegalArgumentException();
}
}
}
2. 表達式求值
Java代碼
/**
* 整數表達式運算
*/
public class EvaluateExpression {
/**
* 表達式
*/
private String expression;
/**
* 最初的表達式
*/
private String initExpression;
/**
* 運算符棧
*/
private MyStack<Character> optr = new MyArrayStack<Character>();
/**
* 操作數棧
*/
private MyStack<Integer> opnd = new MyArrayStack<Integer>();
/**
* 表明下一個是否應該是數字
*/
private boolean numberNext;
public EvaluateExpression(String expression) {
this.expression = expression;
this.initExpression = expression;
numberNext = true;
}
/**
* 求值
*/
public Integer evaluate() {
delBlank();
handleParentheses();
while (true) {
if ("".equals(expression)) {
break;
}
if (expression.matches("^-?\\d+.*$") && numberNext) {
opnd.push(getInteger());
continue;
} else {
Character operand = expression.charAt(0);
numberNext = true;
expression = expression.substring(1);
Character pop = optr.pop();
if (pop == null) {
optr.push(operand);
continue;
} else {
Precede precede = Precede.judgePrecede(pop, operand);
switch (precede) {
// 優先順序高時運算前2個操作數
case LARGER: {
optr.push(operand);
Integer next = opnd.pop();
Integer last = opnd.pop();
evaluateNow(last, pop, next);
break;
}
// 優先順序低時運算前一個操作數和後一個操作數
case LESS: {
optr.push(pop);
Integer last = opnd.pop();
Integer next = getInteger();
evaluateNow(last, operand, next);
break;
}
}
}
}
}
// 運算結果
Integer result = null;
if (optr.length() == 0 && opnd.length() == 1) {
result = opnd.pop();
} else if (optr.length() == 1 && opnd.length() == 2) {
Integer next = opnd.pop();
Integer last = opnd.pop();
evaluateNow(last, optr.pop(), next);
result = opnd.pop();
} else {
throw new RuntimeException();
}
return result;
}
/**
* 進行實際的運算，並將結果入棧
*/
private void evaluateNow(Integer last, Character operand, Integer next) {
switch (operand) {
case '+':
opnd.push(last + next);
break;
case '-':
opnd.push(last - next);
break;
case '*':
opnd.push(last * next);
break;
case '/':
opnd.push(last / next);
break;
}
}
/**
* 獲得表達式開頭部分的整數
*/
private Integer getInteger() {
StringBuilder sb = new StringBuilder();
int count = 0; // 整數位
boolean lessZero = false; // 是否是負數
if (expression.startsWith("-")) {
sb.append("-");
count++;
lessZero = true;
}
int i = (lessZero ? 1 : 0);
for (; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c >= '0' && c <= '9') {
sb.append(c);
count++;
} else {
break;
}
}
expression = expression.substring(count);
numberNext = false;
return Integer.valueOf(sb.toString());
}
/**
* 處理括弧. 將括弧內的字元串作為子表達式計算.
*/
private void handleParentheses() {
while (expression.contains("(")) {
// 左括弧的索引
int left = 0;
// 右括弧的索引
int right = 0;
// 左括弧的數量
int count = 0;
// 求出左括弧索引
left = expression.indexOf('(');
// 求出對應的右括弧索引
for (int i = left; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == ')') {
count--;
// count為0時才是對應的右括弧
if (count == 0) {
right = i;
break;
}
} else if (c == '(') {
count++;
} else {
continue;
}
}
// 左右括弧之間是一個子表達式, 計運算元表達式的值，並根據結果構造出新的表達式
EvaluateExpression evaluateExpression = new EvaluateExpression(expression.substring(left + 1, right));
expression = expression.substring(0, left) + evaluateExpression.evaluate()
+ expression.substring(right + 1);
}
}
/**
* 刪除表達式中的空白字元
*/
private void delBlank() {
expression = expression.replaceAll("\\s", "");
}
@Override
public String toString() {
return initExpression;
}
}
3. 進行測試
Java代碼
@Test
public void testEvaluate() {
EvaluateExpression expression = new EvaluateExpression("1 + 2 ");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("4 + 2 * 3 - 10 / 5");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("(1+2) * (4 + 5) - (9 / 7)");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("(1 + (3 * (4 - 9)))");
System.out.println(expression + " = " + expression.evaluate());
expression = new EvaluateExpression("(1 + (3 * (4 - 9))) + (3 * (2 + 3))");
System.out.println(expression + " = " + expression.evaluate());
}
測試的結果為:
1 + 2 = 3
4 + 2 * 3 - 10 / 5 = 8
(1+2) * (4 + 5) - (9 / 7) = 26
(1 + (3 * (4 - 9))) = -14
(1 + (3 * (4 - 9))) + (3 * (2 + 3)) = 1
5. Java 字元串算術表達式求值
import java.util.ArrayList;
import java.util.Stack;
/**itjob
*
* @author yhh
*
*/
public class Calculate {
/**
* 將字元串轉化成List
* @param str
* @return
*/
public ArrayList<String> getStringList(String str){
ArrayList<String> result = new ArrayList<String>();
String num = "";
for (int i = 0; i < str.length(); i++) {
if(Character.isDigit(str.charAt(i))){
num = num + str.charAt(i);
}else{
if(num != ""){
result.add(num);
}
result.add(str.charAt(i) + "");
num = "";
}
}
if(num != ""){
result.add(num);
}
return result;
}
/**
* 將中綴表達式轉化為後綴表達式
* @param inOrderList
* @return
*/
public ArrayList<String> getPostOrder(ArrayList<String> inOrderList){
ArrayList<String> result = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
for (int i = 0; i < inOrderList.size(); i++) {
if(Character.isDigit(inOrderList.get(i).charAt(0))){
result.add(inOrderList.get(i));
}else{
switch (inOrderList.get(i).charAt(0)) {
case '(':
stack.push(inOrderList.get(i));
break;
case ')':
while (!stack.peek().equals("(")) {
result.add(stack.pop());
}
stack.pop();
break;
default:
while (!stack.isEmpty() && compare(stack.peek(), inOrderList.get(i))){
result.add(stack.pop());
}
stack.push(inOrderList.get(i));
break;
}
}
}
while(!stack.isEmpty()){
result.add(stack.pop());
}
return result;
}
/**
* 計算後綴表達式
* @param postOrder
* @return
*/
public Integer calculate(ArrayList<String> postOrder){
Stack stack = new Stack();
for (int i = 0; i < postOrder.size(); i++) {
if(Character.isDigit(postOrder.get(i).charAt(0))){
stack.push(Integer.parseInt(postOrder.get(i)));
}else{
Integer back = (Integer)stack.pop();
Integer front = (Integer)stack.pop();
Integer res = 0;
switch (postOrder.get(i).charAt(0)) {
case '+':
res = front + back;
break;
case '-':
res = front - back;
break;
case '*':
res = front * back;
break;
case '/':
res = front / back;
break;
}
stack.push(res);
}
}
return (Integer)stack.pop();
}
/**
* 比較運算符等級
* @param peek
* @param cur
* @return
*/
public static boolean compare(String peek, String cur){
if("*".equals(peek) && ("/".equals(cur) || "*".equals(cur) ||"+".equals(cur) ||"-".equals(cur))){
return true;
}else if("/".equals(peek) && ("/".equals(cur) || "*".equals(cur) ||"+".equals(cur) ||"-".equals(cur))){
return true;
}else if("+".equals(peek) && ("+".equals(cur) || "-".equals(cur))){
return true;
}else if("-".equals(peek) && ("+".equals(cur) || "-".equals(cur))){
return true;
}
return false;
}
public static void main(String[] args) {
Calculate calculate = new Calculate();
String s = "12+(23*3-56+7)*(2+90)/2";
ArrayList result = calculate.getStringList(s); //String轉換為List
result = calculate.getPostOrder(result); //中綴變後綴
int i = calculate.calculate(result); //計算
System.out.println(i);
}
}
6. java後綴表達式實現表達式求值
import java.util.Scanner;
import java.util.Stack;
public class 表達式計算 {
private static Stack<String> num = new Stack<String>();//存後綴表達式
private static Stack<String> sign = new Stack<String>();//存入符號
private static Stack<Integer> result = new Stack<Integer>();//放結果
public static void getGroup(String line){//講字元串轉換為後綴表達式
for(int i=0; i<line.length(); i++){
char c = line.charAt(i);
if((int)c>=48 && (int)c<=57){//當遇到數字的時候,判斷是不是多位數，然後在push進num
int j = i+1;
while(j<line.length() && (line.charAt(j)>=48 && line.charAt(j)<=57)){
j++;
}
num.push(line.substring(i, j));
i = j-1;
}else if(c == '('){//遇到左括弧直接存進num
sign.push(String.valueOf(c));
}else if(c == ')'){//遇到右括弧從sign中pop棧頂元素push到num知道遇到'(',然後再pop掉'('
while(!sign.peek().equals("(")){
num.push(sign.pop());
}
sign.pop();
}else{
int n = 0;
if(!sign.empty()){//如果sign中沒有元素，直接令n = 0
n = getNum(sign.peek().charAt(0));
}
int m = getNum(c);
if(m >= n){//如果當前元素的運算級別比棧頂元素運算級別要高，就直接push進sign
sign.push(String.valueOf(c));
}else{
while(m < n){//如果當前運算運算級別比sign棧頂元素運算級別要低，就將sign棧頂元素pop並且push進num，知道不符合條件
num.push(sign.pop());//輸入例子2*3+6/3的時候，這里一直報錯
if(!sign.empty()){
n = getNum(sign.peek().charAt(0));
}else{
n = 0;
}
}
sign.push(String.valueOf(c));
}
}
}
while(!sign.empty()){
num.push(sign.pop());
}
}
private static int getNum(char c){
int n = 0;
switch(c){
case '+':
case '-':
n = 1;
break;
case '*':
case '/':
n = 2;
break;
}
return n;
}
7. 計算器製作JAVA版（第三步，表達式求值（+
1.首先思考一下製作計算器需要哪些Swing組件，下面列出一些製作計算器的一些常用組件：
JFrame Jpanel JButton JTextField
2.選用布局管理器：
這里採用的是GridBagLayout，即網格包布局管理器。
3.如何處理按鈕事件：
這里可以分兩種情況來考慮，一：處理0~9的數字按鈕和"."按鈕，這種按鈕的單擊事件很簡單，只需要獲取監聽的對象，並在文本框中顯示對象的數據即可。
二：處理操作按鈕即文本為+，-，*，/，C（清除），D（刪除）和=的按鈕，這些按鈕的事件處理稍微復雜。
4.具體實現代碼如下：
1.創建Calculator類，該類繼承自JFrame類
[java]view plain
importjava.awt.BorderLayout;
importjava.awt.GridBagConstraints;
importjava.awt.GridBagLayout;
importjava.awt.event.ActionEvent;
importjava.awt.event.ActionListener;
importjavax.swing.JButton;
importjavax.swing.JFrame;
importjavax.swing.JOptionPane;
importjavax.swing.JPanel;
importjavax.swing.JTextField;
{
=1L;
privateJTextFieldjtf=newJTextField();
privateJPanelpanel=newJPanel();
=newGridBagLayout();
=newGridBagConstraints();
privateintselect=0;
//privateStringcommand="";
privatedoubletemp=0.0;
privatedoublenumber;
publicCalculator(){//創建Calculator類的構造方法
this.setTitle("計算器");
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.add(jtf,BorderLayout.NORTH);
this.add(panel,BorderLayout.CENTER);
panel.setLayout(gridbaglayout);//將panel面板設置成網格包布局管理器
this.add(panel);
jtf.setHorizontalAlignment(JTextField.RIGHT);//文本靠右
ActionListenernums=newCalculatorAction1();
ActionListeneropin=newCalculatorAction2();
constraints.fill=GridBagConstraints.BOTH;
//constraints.weightx=0.1;
//constraints.weighty=0.1;
constraints.gridheight=GridBagConstraints.REMAINDER;
addButton("",nums);
constraints.gridheight=1;
addButton("C",opin);
addButton("7",nums);
addButton("4",nums);
addButton("1",nums);
constraints.gridheight=GridBagConstraints.REMAINDER;
addButton("%",nums);
constraints.gridheight=1;
addButton("D",opin);
addButton("8",nums);
addButton("5",nums);
addButton("2",nums);
constraints.gridheight=GridBagConstraints.REMAINDER;
addButton("0",nums);
constraints.gridheight=1;
addButton("/",opin);
addButton("9",nums);
addButton("6",nums);
addButton("3",nums);
constraints.gridheight=GridBagConstraints.REMAINDER;
addButton(".",nums);
constraints.gridheight=1;
addButton("*",opin);
addButton("-",opin);
addButton("+",opin);
constraints.gridheight=GridBagConstraints.REMAINDER;
addButton("=",opin);
}
privatevoidaddButton(Stringstr,ActionListenerlist){//添加按鈕方法
JButtonbutton=newJButton(str);
if(str.equals("")||str.equals("%")){
button.setEnabled(false);
}
button.addActionListener(list);//向按鈕添加事件
gridbaglayout.setConstraints(button,constraints);
panel.add(button);//將按鈕添加到JPanel容器中
}
{//創建內部類並實現ActionListener介面，實現數字按鈕的監聽事件
publicvoidactionPerformed(ActionEvente){
Stringinput=e.getActionCommand();
//System.out.println(input);
jtf.setText(jtf.getText()+input);//在文本中顯示用戶單擊的按鈕文本內容
}
}
{//創建內部類並實現ActionListener介面，實現操作按鈕的監聽事件
publicvoidactionPerformed(ActionEvente){
Stringcommand=e.getActionCommand();
if(command.equals("+")){
temp=Double.parseDouble(jtf.getText());
jtf.setText("");
select=1;
}
if(command.equals("-")){
temp=Double.parseDouble(jtf.getText());
jtf.setText("");
select=2;
}
if(command.equals("*")){
temp=Double.parseDouble(jtf.getText());
jtf.setText("");
select=3;
}
if(command.equals("/")){
temp=Double.parseDouble(jtf.getText());
jtf.setText("");
select=4;
}
if(command.equals("C")){
jtf.setText("");
}
if(command.equals("D")){
jtf.setText(jtf.getText().substring(0,jtf.getText().length()-1));
}
if(command.equals("=")){
if(select==1){
number=Double.parseDouble(jtf.getText());
jtf.setText((temp+number)+"");
}
elseif(select==2){
number=Double.parseDouble(jtf.getText());
jtf.setText((temp-number)+"");
}
elseif(select==3){
number=Double.parseDouble(jtf.getText());
jtf.setText((temp*number)+"");
}
elseif(select==4){
number=Double.parseDouble(jtf.getText());
if(number==0){
JOptionPane.showMessageDialog(panel,"除數不能為0");
}
else
jtf.setText((temp/number)+"");
}
}
}
}
}
2.創建CalculatorTest類
[java]view plain
publicclassCalculatorTest{
publicstaticvoidmain(String[]args){
CalculatormainFrame=newCalculator();
mainFrame.setBounds(300,200,200,200);
mainFrame.setVisible(true);
mainFrame.setResizable(false);
}
}
閱讀全文
8. 藍橋杯演算法訓練 java演算法 表達式求值
這兩天看到的內容是關於棧和隊列，在棧的模塊發現了Dijkstra雙棧算術表達式求值演算法，可以用來實現計算器類型的app。
編程語言系統一般都內置了對算術表達式的處理，但是他們是如何在內部實現的呢？為了了解這個過程，我們可以自行搭建一套簡易的算術表達式處理機制，這里就用到棧特性和本篇提到的Dijkstra演算法。
概述：
算術表達式可能是一個數、或者是由一個左括弧、一個算術表達式、一個運算符、另一個算術表達式和一個右括弧組成的表達式。為了簡化問題，這里定義的是未省略括弧的算術表達式，它明確地說明了所有運算符的操作數，形式如下：
（1+（（2+3）*（4*5）））
思路：
表達式由括弧、運算符和操作數構成，我們根據以下4中情況從左至右逐個將這些實體送入棧處理：
1.將操作數壓入操作數棧；
2.將運算符壓入運算符棧；
3.忽略左括弧；
4.在遇到右括弧時，彈出一個運算符，彈出所需數量的操作數，並將運算後的結果壓入操作數棧；
在處理完最後一個右括弧時，操作數棧上只會剩下一個值，它就是表達式的計算結果。這種方法咋一看難理解，但要證明它能計算得到正確的值很簡單：
每當演算法遇到一個括弧包圍，並由一個運算符和兩個操作數組成的子式時，他都將運算符和操作數運算結果壓入操作數棧。這樣的結果就像是在輸入中用這個值代替了該子表達式，因此用這個值代替子表達式得到的結果和原表達式相同。我們可以反復應用這個規律並得到一個最終值。
例如：
（1+（（2+3）*（4*5）））
（1+（5*（4*5）））
（1+（5*20））
（1+100）
101
代碼實現：
這里我採用C#來實現，最終運行效果完全符合預期，證明了此演算法的正確性，代碼如下：
using System;
using System.Collections.Generic;
using System.Linq;
namespace Evaluate
{
class Program
{
static void Main(string[] args)
{
string testExpress = "(1+((2+3)*(4*5)))";
Console.WriteLine(Evaluate(testExpress));
}
//DijkStra
static double Evaluate(string express)
{
var expressChars = express.ToArray();
Stack ops = new Stack();
Stack vals = new Stack();
if (express.Length > 0)
{
foreach (var opt in expressChars)
{
switch (opt)
{
case '+':
case '-':
case '*':
case '/':
ops.Push(opt);
break;
case ')':
var op = ops.Pop();
var v = vals.Pop();
switch (op)
{
case '+':
v += vals.Pop();
break;
case '-':
v = vals.Pop() - v;
break;
case '*':
v *= vals.Pop();
break;
case '/':
v = vals.Pop() / v;
break;
}
vals.Push(v);
break;
case ' ':
case '(':
break;
default:
vals.Push(double.Parse(opt.ToString()));
break;
}
}
return vals.Pop();
}
return double.MaxValue;
}
}
}
總結：
Dijkstra演算法充分利用了棧的特性，具備較高的執行效率，經過進一步的擴充修改，就完全可以實現具備科學計算功能的復雜計算類app。如果大家還有更好的，更適用的演算法，歡迎在評論中給出地址，謝謝。
轉載
9. 表達式求值 逆波蘭表達式演算法 java版
表達式求值 逆波蘭表達式演算法 如下：
import java.util.ArrayList;
import java.util.List;
public class MyStack {
private List<String> l;
private int size;
public String top;
public MyStack() {
l = new ArrayList<String>();
size = 0;
top = null;
}
public int size() {
return size;
}
public void push(String s) {
l.add(s);
top = s;
size++;
}
public String pop() {
String s = l.get(size - 1);
l.remove(size - 1);
size--;
top = size == 0 ? null : l.get(size - 1);
return s;
}
}
import java.util.ArrayList;
import java.util.List;
public class Nbl {
private static MyStack ms1 = new MyStack();//生成逆波蘭表達式的棧
private static MyStack ms2 = new MyStack();//運算棧
/**
* 將字元串轉換為中序表達式
*/
public static List<String> zb(String s) {
List<String> ls = new ArrayList<String>();//存儲中序表達式
int i = 0;
String str;
char c;
do {
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
ls.add("" + c);
i++;
} else {
str = "";
while (i < s.length() && (c = s.charAt(i)) >= 48
&& (c = s.charAt(i)) <= 57) {
str += c;
i++;
}
ls.add(str);
}
} while (i < s.length());
return ls;
}
/**
* 將中序表達式轉換為逆波蘭表達式
*/
public static List<String> parse(List<String> ls) {
List<String> lss = new ArrayList<String>();
for (String ss : ls) {
if (ss.matches("\d+")) {
lss.add(ss);
} else if (ss.equals("(")) {
ms1.push(ss);
} else if (ss.equals(")")) {
while (!ms1.top.equals("(")) {
lss.add(ms1.pop());
}
ms1.pop();
} else {
while (ms1.size() != 0 && getValue(ms1.top) >= getValue(ss)) {
lss.add(ms1.pop());
}
ms1.push(ss);
}
}
while (ms1.size() != 0) {
lss.add(ms1.pop());
}
return lss;
}
/**
* 對逆波蘭表達式進行求值
*/
public static int jisuan(List<String> ls) {
for (String s : ls) {
if (s.matches("\d+")) {
ms2.push(s);
} else {
int b = Integer.parseInt(ms2.pop());
int a = Integer.parseInt(ms2.pop());
if (s.equals("+")) {
a = a + b;
} else if (s.equals("-")) {
a = a - b;
} else if (s.equals("*")) {
a = a * b;
} else if (s.equals("\")) {
a = a / b;
}
ms2.push("" + a);
}
}
return Integer.parseInt(ms2.pop());
}
/**
* 獲取運算符優先順序
* +,-為1 *,/為2 ()為0
*/
public static int getValue(String s) {
if (s.equals("+")) {
return 1;
} else if (s.equals("-")) {
return 1;
} else if (s.equals("*")) {
return 2;
} else if (s.equals("\")) {
return 2;
}
return 0;
}
public static void main(String[] args) {
System.out.println(jisuan(parse(zb("0-8+((1+2)*4)-3+(2*7-2+2)"))));
}
}
10. java實現算術表達式求值
import java.util.Collections;
import java.util.Stack;
public class Calculator {
private Stack<String> postfixStack = new Stack<String>();//後綴式棧
private Stack<Character> opStack = new Stack<Character>();//運算符棧
private int [] operatPriority = new int[] {0,3,2,1,-1,1,0,2};//運用運算符ASCII碼-40做索引的運算符優先順序
public static void main(String[] args) {
System.out.println(5+12*(3+5)/7.0);
Calculator cal = new Calculator();
String s = "5+12*(3+5)/7";
double result = cal.calculate(s);
System.out.println(result);
}
/**
* 按照給定的表達式計算
* @param expression 要計算的表達式例如:5+12*(3+5)/7
* @return
*/
public double calculate(String expression) {
Stack<String> resultStack = new Stack<String>();
prepare(expression);
Collections.reverse(postfixStack);//將後綴式棧反轉
String firstValue ,secondValue,currentValue;//參與計算的第一個值，第二個值和算術運算符
while(!postfixStack.isEmpty()) {
currentValue = postfixStack.pop();
if(!isOperator(currentValue.charAt(0))) {//如果不是運算符則存入操作數棧中
resultStack.push(currentValue);
} else {//如果是運算符則從操作數棧中取兩個值和該數值一起參與運算
secondValue = resultStack.pop();
firstValue = resultStack.pop();
String tempResult = calculate(firstValue, secondValue, currentValue.charAt(0));
resultStack.push(tempResult);
}
}
return Double.valueOf(resultStack.pop());
}
/**
* 數據准備階段將表達式轉換成為後綴式棧
* @param expression
*/
private void prepare(String expression) {
opStack.push(',');//運算符放入棧底元素逗號，此符號優先順序最低
char[] arr = expression.toCharArray();
int currentIndex = 0;//當前字元的位置
int count = 0;//上次算術運算符到本次算術運算符的字元的長度便於或者之間的數值
char currentOp ,peekOp;//當前操作符和棧頂操作符
for(int i=0;i<arr.length;i++) {
currentOp = arr[i];
if(isOperator(currentOp)) {//如果當前字元是運算符
if(count > 0) {
postfixStack.push(new String(arr,currentIndex,count));//取兩個運算符之間的數字
}
peekOp = opStack.peek();
if(currentOp == ')') {//遇到反括弧則將運算符棧中的元素移除到後綴式棧中直到遇到左括弧
while(opStack.peek() != '(') {
postfixStack.push(String.valueOf(opStack.pop()));
}
opStack.pop();
} else {
while(currentOp != '(' && peekOp != ',' && compare(currentOp,peekOp) ) {
postfixStack.push(String.valueOf(opStack.pop()));
peekOp = opStack.peek();
}
opStack.push(currentOp);
}
count = 0;
currentIndex = i+1;
} else {
count++;
}
}
if(count > 1 || (count == 1 && !isOperator(arr[currentIndex]))) {//最後一個字元不是括弧或者其他運算符的則加入後綴式棧中
postfixStack.push(new String(arr,currentIndex,count));
}
while(opStack.peek() != ',') {
postfixStack.push(String.valueOf( opStack.pop()));//將操作符棧中的剩餘的元素添加到後綴式棧中
}
}
/**
* 判斷是否為算術符號
* @param c
* @return
*/
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' ||c == ')';
}
/**
* 利用ASCII碼-40做下標去算術符號優先順序
* @param cur
* @param peek
* @return
*/
public boolean compare(char cur,char peek) {// 如果是peek優先順序高於cur，返回true，默認都是peek優先順序要低
boolean result = false;
if(operatPriority[(peek)-40] >= operatPriority[(cur) - 40]) {
result = true;
}
return result;
}
/**
* 按照給定的算術運算符做計算
* @param firstValue
* @param secondValue
* @param currentOp
* @return
*/
private String calculate(String firstValue,String secondValue,char currentOp) {
String result = "";
switch(currentOp) {
case '+':
result = String.valueOf(ArithHelper.add(firstValue, secondValue));
break;
case '-':
result = String.valueOf(ArithHelper.sub(firstValue, secondValue));
break;
case '*':
result = String.valueOf(ArithHelper.mul(firstValue, secondValue));
break;
case '/':
result = String.valueOf(ArithHelper.div(firstValue, secondValue));
break;
}
return result;
}
}
public class ArithHelper {
// 默認除法運算精度
private static final int DEF_DIV_SCALE = 16;
// 這個類不能實例化
private ArithHelper() {
}
/**
* 提供精確的加法運算。
*
* @param v1 被加數
* @param v2 加數
* @return 兩個參數的和
*/
public static double add(double v1, double v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));
java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));
return b1.add(b2).doubleValue();
}
public static double add(String v1, String v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(v1);
java.math.BigDecimal b2 = new java.math.BigDecimal(v2);
return b1.add(b2).doubleValue();
}
/**
* 提供精確的減法運算。
*
* @param v1 被減數
* @param v2 減數
* @return 兩個參數的差
*/
public static double sub(double v1, double v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));
java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));
return b1.subtract(b2).doubleValue();
}
public static double sub(String v1, String v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(v1);
java.math.BigDecimal b2 = new java.math.BigDecimal(v2);
return b1.subtract(b2).doubleValue();
}
/**
* 提供精確的乘法運算。
*
* @param v1
* 被乘數
* @param v2
* 乘數
* @return 兩個參數的積
*/
public static double mul(double v1, double v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));
java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));
return b1.multiply(b2).doubleValue();
}
public static double mul(String v1, String v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(v1);
java.math.BigDecimal b2 = new java.math.BigDecimal(v2);
return b1.multiply(b2).doubleValue();
}
/**
* 提供（相對）精確的除法運算，當發生除不盡的情況時，精確到 小數點以後10位，以後的數字四捨五入。
*
* @param v1
* 被除數
* @param v2
* 除數
* @return 兩個參數的商
*/
public static double div(double v1, double v2) {
return div(v1, v2, DEF_DIV_SCALE);
}
public static double div(String v1, String v2) {
java.math.BigDecimal b1 = new java.math.BigDecimal(v1);
java.math.BigDecimal b2 = new java.math.BigDecimal(v2);
return b1.divide(b2, DEF_DIV_SCALE, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();
}
/**
* 提供（相對）精確的除法運算。當發生除不盡的情況時，由scale參數指 定精度，以後的數字四捨五入。
*
* @param v1 被除數
* @param v2 除數
* @param scale 表示表示需要精確到小數點以後幾位。
* @return 兩個參數的商
*/
public static double div(double v1, double v2, int scale) {
if (scale < 0) {
throw new IllegalArgumentException("The scale must be a positive integer or zero");
}
java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));
java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));
return b1.divide(b2, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();
}
/**
* 提供精確的小數位四捨五入處理。
*
* @param v 需要四捨五入的數字
* @param scale 小數點後保留幾位
* @return 四捨五入後的結果
*/
public static double round(double v, int scale) {
if (scale < 0) {
throw new IllegalArgumentException("The scale must be a positive integer or zero");
}
java.math.BigDecimal b = new java.math.BigDecimal(Double.toString(v));
java.math.BigDecimal one = new java.math.BigDecimal("1");
return b.divide(one, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();
}
public static double round(String v, int scale) {
if (scale < 0) {
throw new IllegalArgumentException("The scale must be a positive integer or zero");
}
java.math.BigDecimal b = new java.math.BigDecimal(v);
java.math.BigDecimal one = new java.math.BigDecimal("1");
return b.divide(one, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();
}
}