实现简单的算术表达式

算术表达式"/>

实现简单的算术表达式

这里用栈的数据结构实现算术表达式（简单起见，这里定义的是未省略括号的算术表达式，支持+、-、*、/）。
E.W.Dijkstra在20世纪60年代发明了一个简单算法，用两个栈（一个用于保存运算符，一个用于保存操作数）完成了这个任务。表达式由括号、运算符和操作数组成，根据以下4种情况从左到右逐个将这些实体送入栈处理：
1.将操作数压入操作数栈；
2.将运算符压入运算符栈；
3.忽略左括号；
4.在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。
在处理完最后一个右括号之后，操作数栈上只会有一个值，即表达式的值。
java实现代码如下：

import java.util.Scanner;
import java.util.Stack;public class Evaluate {public static double evalute(String str){Stack<Character> ops = new Stack<Character>();//操作数栈Stack<Double> vals = new Stack<Double>();//操作符栈for(int i = 0; i < str.length(); i++){char c = str.charAt(i);//读取字符，如果是运算符则压入运算符栈if(c == '(' || c == ' '){//忽略左括号}else if(c == '+' || c == '-' || c == '*' || c == '/'){ops.push(c);}else if(c == ')'){//如果字符为')'，弹出运算符和操作数，计算结果并压入栈char op = ops.pop();double v = vals.pop();if(op == '+'){v += vals.pop();}else if(op == '-'){v -= vals.pop();}else if(op == '*'){v *= vals.pop();}else if(op == '/'){v /= vals.pop();}vals.push(v);}else{//如果字符不是括号，不是运算符，也不是空格，则作为double值压入操作数栈vals.push((double)(c - '0'));}}return vals.pop();}public static void main(String[] args){//输入的操作数只能是一位数System.out.println("请输入表达式：");Scanner in = new Scanner(System.in);String str = in.nextLine();System.out.println(str + "=" + evalute(str));}
}

运行结果：

注意：由于本代码用字符获得输入字符串中的每个字符，所以操作数只能是一位数。