简易版计算器
功能：计算一个简单字符串的值
所输入的字符串仅包含‘+’、‘-’、‘*’、‘/’、‘(’、’)’以命令行的形式输入和呈现效果
知识点
中缀表达式转逆波兰式 – 编译原理Queue、Stack基于Java
中缀转换方式:
从左到右进行遍历运算数,直接输出到队列左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈)右括号,(意味着括号已结束)不断弹出栈顶运算符并输出至队列直到遇到左括号(弹出但不输出)运算符,将该运算符与栈顶运算符进行比较, 1）如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行), 2）如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符. (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算) 直到优先级大于栈顶运算符或者栈空,再将该运算符入栈.如果对象处理完毕,则按顺序弹出并输出栈中所有运算符入队列.
计算逆波兰式:
判断队头元素，数字即入栈如果是运算符，计算结果并结果入栈直至队列为空，此时栈顶元素即为目标值
import java.util.*;
/**
*
* @author 路瞳
* @email : 2326713669@qq.com
* @date 10/6/2020
* @function
* 0、计算一个简单字符串的值(仅包含‘+’、‘-’、‘*’、‘/’、‘(’、')')
* 1、首先利用栈将中缀表示式转换为后缀表达式即逆波兰式
* 2、后缀表达式求解
*
* @result
* 能够完成0~9的加减乘除，返回值为一个double类型
*/
public class Calculating {
private String tar;
private Stack<Character> stack = new Stack<Character>();
// //this string can be calculated
// private boolean isTrue = true;
//
Calculating(String string) {
this.tar = string;
}
// public boolean getRes() {
// return this.isTrue;
// }
/**
*
* @return return a repolish queue
*/
private Queue<Character> transToRePolish() {
char[] chars = tar.toCharArray();
Queue<Character> queue = new LinkedList<Character>();
for (char ch : chars) {
if (isNum(ch)) {
queue.offer(ch);
} else if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
while (stack.peek() != '(') {
queue.offer(stack.pop());
}
if (stack.peek() == '(') {
stack.pop();
}
} else if (isOp(ch)) {
if(stack.isEmpty()){
stack.push(ch);
continue;
}
if (!compPriority(ch, stack.peek())) {
while (!stack.isEmpty() && !compPriority(ch, stack.peek())) {
queue.offer(stack.pop());
}
}
stack.push(ch);
}
}
while(!stack.isEmpty()){
queue.offer(stack.pop());
}
return queue;
}
/**
*
* @param queue
* @return result
*/
private double calRepolish(Queue<Character> queue){
Stack<Integer> res = new Stack<Integer>();
while (!queue.isEmpty()){
Character t = queue.poll();
if(t.equals('+') || t.equals('-') || t.equals('*') || t.equals('/')){
int a = res.pop();
int b = res.pop();
int result = cal(b, a, t);
res.push(result);
}else{
res.push(t-48);
}
}
return res.pop();
}
private int cal(int a, int b, Character t) {
//计算
if(t.equals('+')){
return a + b;
}else if(t.equals('-')){
return a - b;
}else if(t.equals('*')){
return a * b;
}else{
return a / b;
}
}
boolean isNum(char ch) {
if (ch < '0' || ch > '9') {
return false;
}
return true;
}
boolean isOp(char ch) {
if (ch == '*' || ch == '/' || ch == '+' || ch == '-') {
return true;
} else {
return false;
}
}
/**
* @param fir target
* @param sec stack top elemnt
* @return priority
*/
boolean compPriority(char fir, char sec) {
if(sec == '('){
return true;
}
// int f = 0;
// int s = 0;
// if (fir == '*' || fir == '/') {
// f = 2;
// }
// if (sec == '*' || sec == '/') {
// s = 2;
// }
// if (fir == '+' || fir == '-') {
// f = 1;
// }
// if (sec == '+' || sec == '-') {
// s = 1;
// }
if((fir == '*' || fir == '/') && (sec == '+' || sec == '-')){
return true;
}
else {
return false;
}
//优先级高于栈顶，压入堆栈
// return f > s ? true : false;
}
public double calculte() {
Queue<Character> repolish = transToRePolish();
System.out.println(repolish);
double result = calRepolish(repolish);
System.out.println(result);
return result;
}
/**
* just for test
*/
public static void main(String[] args) {
Calculating ca = new Calculating("3*8+3+2");
ca.calculte();
}
}
参考资料： 1、中缀表达式转逆波兰式 2、数据结构 （C语言版）
