package come.feiqiang.stack;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;
public class Algorithm {
/**
* 验证各种括号的匹配问题,是对栈的基本应用:
* @param expression
* @return
*/
public static boolean isBalanced(String expression){
final char LEFT_NOMAL='(';
final char RIGHT_NOMAL=')';
final char LEFT_CURLY='{';
final char RIGHT_CURLY='}';
final char LEFT_SQUARE='[';
final char RIGHT_SQUARE=']';
Stack<Character> store=new Stack<Character>();
int i;
boolean failed=false;
for(i=0;!failed&&i<expression.length();i++){
switch(expression.charAt(i)){
case LEFT_NOMAL:
case LEFT_CURLY:
case LEFT_SQUARE:
store.push(expression.charAt(i));
break;
case RIGHT_NOMAL:
if(store.isEmpty()||store.pop()!=LEFT_NOMAL){
failed=true;
}
break;
case RIGHT_CURLY:
if(store.isEmpty()||store.pop()!=LEFT_CURLY){
failed=true;
}
break;
case RIGHT_SQUARE:
if(store.isEmpty()||store.pop()!=LEFT_SQUARE){
failed=true;
}
break;
}
}
return (store.isEmpty()&&!failed);
}
/**
* 计算完全加括号的算术:
* @param numbers 数字栈
* @param operations 操作符栈
* 算法:
* do
* if(下一个输入是数值)
* 进数值栈
else if(下一个输入是操作符)
* 进操作符栈
* else if(下一个输入是右括号)
* 弹出两个数值,弹出一个操作符,将后弹出的数值与前弹出的数值作运算,将操作结果压入数值栈
* 如果栈为空,或操作数为空,抛出异常
* else if(下一个输入是左括号)
* 跳过
* else 抛出非法字符异常
*while(还有更多输入)
* 算法缺点:没有检查括号的正确匹配情况,有兴趣的读者可以自己研究一下
*
*/
public static void evaluateStackTops(Stack<Double> numbers, Stack<Character> operations){
double operand1;
double operand2;
operand1=numbers.pop();
operand2=numbers.pop();
char operation=operations.pop();
switch(operation){
case '+':
numbers.push(operand1+operand2);
break;
case '-':
numbers.push(operand1-operand2);
break;
case '*':
numbers.push(operand1*operand2);
break;
case '/':
numbers.push(operand1/operand2);
break;
default:
throw new IllegalArgumentException("Illegal Operation");
}
}
public static double evaluate(String expression){
Stack<Double> numbers=new Stack<Double>();
Stack<Character> operations=new Stack<Character>();
Scanner input=new Scanner(expression);
String next;
final Pattern CHARACTER=Pattern.compile("\\S.*?");
final Pattern UNSIGN_DOUBLE=Pattern.compile("(((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?)");
while(input.hasNext()){
if(input.hasNext(UNSIGN_DOUBLE)){
next=input.findInLine(UNSIGN_DOUBLE);
numbers.push(new Double(next));
}
else{
next=input.findInLine(CHARACTER);
switch(next.charAt(0)){
case '+':
case '-':
case '*':
case '/':
operations.push(next.charAt(0));
break;
case ')':
evaluateStackTops(numbers,operations);
break;
case '(':
break;
default:
throw new IllegalArgumentException("Illegal character");
}
}
}
if(numbers.size()!=1){
throw new IllegalArgumentException("Illegal input Exception");
}
return numbers.pop();
}
/**
* 后缀表达式的计算:
* @param expression
* @return
* 算法:
* 初始化一个由双精度实数构成的栈
* while(表达式中有更多输入)
* if(下一个输入是数值)
* 读取下一个元素并压入栈中
* else
* (下一个输入是操作符)
* 弹出两个操作数,根据操作符运算后将结果压入栈中
* while end
*
*/
public static double evaluatePostfix(String expression){
double answer;
Scanner scanner=new Scanner(expression);
Stack<Double> numbers=new Stack<Double>();
Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?");
Pattern CHARACTER=Pattern.compile("\\S.*?");
while(scanner.hasNext()){
if(scanner.hasNext(UNSIGN_DOUBLE)){
numbers.push(new Double(scanner.findInLine(UNSIGN_DOUBLE)));
}
else if(scanner.hasNext(CHARACTER)){
double operand2=numbers.pop();
double operand1=numbers.pop();
switch(scanner.findInLine(CHARACTER).charAt(0)){
case '+':numbers.push(operand1+operand2);break;
case '-':numbers.push(operand1-operand2);break;
case '*':numbers.push(operand1*operand2);break;
case '/':numbers.push(operand1/operand2);break;
default:throw new IllegalArgumentException("the expression is't right");
}
}
else{
throw new IllegalArgumentException("the expression is't right");
}
}
if(numbers.size()!=1){
throw new IllegalArgumentException("illegal expression");
}
answer=numbers.pop();
return answer;
}
/**
* 由普通的中缀表达是转化为后缀表达式:
* @param expression
* @return
* 算法:
* 略
*/
public static String convertMidToPost(String expression){
String answer="";
Stack<Character> operations=new Stack<Character>();
Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?");
Pattern CHARACTER=Pattern.compile("\\S.*?");
Scanner scanner=new Scanner(expression);
while(scanner.hasNext()){
if(scanner.hasNext(UNSIGN_DOUBLE)){
answer+=scanner.findInLine(UNSIGN_DOUBLE)+" ";
}
else{
char m;
if(scanner.hasNext(CHARACTER)){
switch((m=scanner.findInLine(CHARACTER).charAt(0))){
case '+':
case '-':
case '*':
case '/':
case '(':
operations.push(m);break;
case ')':
char c=operations.pop();
if((operations.isEmpty())||(c!='+'&&c!='-'&&c!='*'&&c!='/')){
throw new IllegalArgumentException("not valid expression");
}
answer+=String.valueOf(c)+" ";
if(operations.pop()!='('){
throw new IllegalArgumentException("not valid expression");
}
break;
default:
throw new IllegalArgumentException("not valid expression");
}
}
}
}
return answer;
}
/**
* 带有优先级的中缀表达式的求解
* @param expression
* @return
* 算法:
* 初始化一个空字符串和一个字符栈
* while(表达式还有更多输入)
* if(下一个输入为数值)
* 读取下一个输入,并入字符串尾部
* else
* if(下一个输入是优先级较高的(*,/)运算符||当前栈为空||当前栈顶元素为'(')
* 读取字符下一个输入符号
* else if(下一个输入是'(')
* 读取字符并且压入栈中
* else if(下一个输入是')')
* 将当前栈中元素全部加入字符串尾部
* else if(下一个输入是运算符)
* 将栈中的符号弹出,并入字符串尾部
* 读取下一个字符串,并且压入栈中
* else
* 弹出非法表达是一茶馆
* while end
*
* 下面的代码与算法稍有差别,因为算法是后写的,所以算法的入错能力更强
*/
public static String priorityOfMid(String expression){
String answer="";
Scanner scanner=new Scanner(expression);
Pattern UNSIGN_DOUBLE=Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][+-]?\\d+)?.*?");
Pattern CHARACTER=Pattern.compile("\\S.*?");
Stack<Character> operations=new Stack<Character>();
if(!scanner.hasNext()){
throw new IllegalArgumentException("illegal exception");
}
while(scanner.hasNext()){
if(scanner.hasNext(UNSIGN_DOUBLE)){
answer+=scanner.findInLine(UNSIGN_DOUBLE)+" ";
}else{
char occurrence=scanner.findInLine(CHARACTER).charAt(0);
if((operations.isEmpty()||operations.peek()=='(')||(occurrence=='*'||occurrence=='/')&&(operations.peek()=='+'||operations.peek()=='-')){
System.out.println("in 1");
operations.push(occurrence);
}else if(occurrence=='('){
operations.push(occurrence);
System.out.println("in 2");
}else if(occurrence==')'){
System.out.println("in 3");
while(!operations.isEmpty()&&operations.peek()!='('){
answer+=String.valueOf(operations.pop())+" ";
}
if(operations.pop()!='('){
throw new IllegalArgumentException("illegal exception");
}
}
else{
System.out.println("in 4");
answer+=operations.pop()+" ";
operations.push(occurrence);
}
}
}
while(!operations.isEmpty()){
answer+=operations.pop()+" ";
}
scanner.close();
return answer;
}
public static void main(String args[]){
//System.out.println(evaluate("(((2+3)+3)*3)"));
//System.out.println("concequence:"+evaluatePostfix("2 3.0*5-6/"));
String midExpression="2";
String postExpression=priorityOfMid(midExpression);
System.out.println("postExpression:"+postExpression);
System.out.print(midExpression+"=");
double x=evaluatePostfix(postExpression);
System.out.println(x);
}
}
分享到:
相关推荐
基于CCS2000的仿真实验报告以及实验代码,详细介绍了利用CCS软件实现算术运算的方法
小学算术运算测试程序,JAVA课程设计报告,有基本代码
本pdf文档介绍了计算机算术运算的原理、结构与设计。从简单的各类加减法到各种算法实现的乘法器、除法器,以及一些浮点运算、函数运算等等。深入浅出的解扰各种实现方法,帮你快速入门。作为手头一个全面的查找手册...
C高级语言程序设计:03算术运算与逻辑运算.pptx
java课程设计 设计一个图形界面的计算器,完成简单的算术运算.docxjava课程设计 设计一个图形界面的计算器,完成简单的算术运算.docxjava课程设计 设计一个图形界面的计算器,完成简单的算术运算.docxjava课程设计 设计...
对于基本的算术表达式,以字符序列的形式从终端进行输入,要求语法正确的,不含变量,按照算术运算优先级顺序,实现基本算术表达式的运算过程。 (1) 输入:输入一个算术表达式,以#结束 (2) 输出:输出数据栈...
简单的算术运算,完成两个值相加的小程序,有刚入门的小同学跟我要,就分享一下。
本pdf文档介绍了计算机算术运算的原理、结构与设计。 从简单的各类加减法到各种算法实现的乘法器、除法器,以及一些浮点运算、函数运算等等。深入浅出的解扰各种实现方法。 主要包含以下四个领域: 基数算术运算,带...
算术运算类指令.docx
学习数据传送和算术运算指令的用法 。 二、 实验内容 将两个多位十进制数28056、47193相加,并显示加数、被加数、和。要求两个加数均以ASCII码形式各自顺序存放在DATA1和DATA2内存单元中,结果送回DATA1处(低位...
「8位算术逻辑运算实验」.pdf「8位算术逻辑运算实验」.pdf「8位算术逻辑运算实验」.pdf「8位算术逻辑运算实验」.pdf「8位算术逻辑运算实验」.pdf「8位算术逻辑运算实验」.pdf「8位算术逻辑运算实验」.pdf「8位算术...
8051算术逻辑运算单元设计8051算术逻辑运算单元设计8051算术逻辑运算单元设计8051算术逻辑运算单元设计8051算术逻辑运算单元设计8051算术逻辑运算单元设计8051算术逻辑运算单元设计8051算术逻辑运算单元设计
数电课程设计,算术运算单元alu的搭建小论文
计算机经典教材,黄凯专著,计算机算术运算原理、结构与设计
ALU能进行多种算术运算和逻辑运算。4位ALU-74LS181能进行16种算术运算和逻辑运算。 (1).掌握算术逻辑单元(ALU)的工作原理; (2).熟悉简单运算器的数据传送通路; (3).画出逻辑电路图及布出美观整齐的接线图...
华中科技大学计算机组成原理实验二运算器实验Logisim源文件,里面有8位可控加减法器设计、32位算术逻辑运算单元ALU设计、四位先行进位74182、四位快速加法器 、8位快速加法器、16位快速加法器、5位阵列乘法、6位补码...
(1) 建立试题库文件,随机产生n个题目; (2) 题目涉及加减乘除,带括号的整数混合运算; (3) 随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价... (假设这是一个可供小学生练习算术运算的小系统)