import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
*
*/
/**
* @author *
*/
public class PostfixEvaluator {
/**
* 将表达式分解成操作数和操作符数组
* @param string
* @return
*/
public static String[] parseExpress(String string)
{
string = string.replaceAll("\\+", " + ");
string = string.replaceAll("-", " - ");
string = string.replaceAll("\\*", " * ");
string = string.replaceAll("/", " / ");
String[] array = string.split(" ");
System.out.println(Arrays.toString(array));
return array;
}
/**
* 将中缀表达式数组转换成后缀栈
* @param infixArray
* @return
*/
public static List<String> infixToPostfix(String[] infixArray)
{
List<String> list = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
//按顺序遍历符号
for (String str : infixArray)
{
if (0 == oprLevel(str))
{
//如果是操作数,直接输出
list.add(str);
}
else if ( stack.isEmpty() || (oprLevel(str) > oprLevel(stack.peek())))
{
//如果栈为空,或符号的优先级比栈顶的符号优先级高,直接入栈
stack.push(str);
}
else
{
//如果栈不为空,并且符号优先级小于等于栈顶符号优先级,先弹出并输出栈顶符号,
//直到栈为空或符号优先级比栈顶的符号优先级高,然后再将当前符号入栈
while(!stack.isEmpty() && (oprLevel(str) <= oprLevel(stack.peek())))
{
list.add(stack.pop());
}
stack.push(str);
}
}
//所有符号都遍历了,如果栈中还有符号,弹出并输出
while (!stack.isEmpty())
{
list.add(stack.pop());
}
System.out.println(list);
//返回后缀表示输出
return list;
}
/**
* 操作数或操作符类型
* @param str
* @return 0 : 操作数
* 1 : 加减
* 2 : 乘除
*/
public static int oprLevel(String str)
{
if (str.equals("*") || str.equals("/"))
{
return 2;
}
else if (str.equals("+") || str.equals("-"))
{
return 1;
}
else
{
return 0;
}
}
/**
* 计算后缀表达式
* @param postfix
* @return
*/
public static int calculatePostfix(String[] postfix)
{
Stack<Integer> stack = new Stack<Integer>();
for (String token : postfix)
{
if ( 0 == oprLevel(token))
{
stack.push(Integer.parseInt(token));
}
else
{
int result = applyOpr(token, stack.pop(), stack.pop());
stack.push(result);
}
}
if (stack.size() != 1)
{
throw new IllegalArgumentException("后缀表达式计算错误" + Arrays.toString(postfix));
}
return stack.pop();
}
/**
* 应用操作符进行计算
* @param opr
* @param second
* @param first
* @return
*/
public static int applyOpr(String opr, int second, int first)
{
int result;
char oprChar = opr.charAt(0);
switch (oprChar) {
case '+':
result = first + second;
break;
case '-':
result = first - second;
break;
case '*':
result = first * second;
break;
case '/':
result = first / second;
break;
default:
throw new IllegalArgumentException("操作符'" + opr + "'错误");
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
String[] array = PostfixEvaluator.parseExpress("100+20*30-200/10");
// System.out.println("预期[100,20,30,*,+,200,10,/,-]");
List<String> list = PostfixEvaluator.infixToPostfix(array);
int result = calculatePostfix(list.toArray(new String[list.size()]));
System.out.println(result);
// String[] array2 = PostfixEvaluator.parseExpress("a+b*c-d");
// System.out.println("预期[a,b,c,*,+,d,-]");
// List<String> list2 = PostfixEvaluator.infixToPostfix(array2);
}
}
分享到:
相关推荐
表达式计算器 采用堆債转换后缀表达式的计算方法 win API ,C++编写 vs2010工程
输入一个字符串形式的四则运算表达式,如"1.0+2.1*(3+4)" 直接谈出结果,输入在文件底部,自己写的。思路是先把中缀表达式转成后缀表达式,然后根据后缀表达式建立一个栈求出结果
充分利用STL的强大功能实现了后缀表达式的计算,不仅支持简单的四则运算,还支持有括号的运算,比如(1+2)*3-4*(2+3)
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算顺序的括号要...
利用运算符优先关系,实现对算术四则混合运算表达式的求值。 【测试数据】 (1)能够判断表达式中的括号是否匹配,测试的表达式中括号不匹配,可以重新输入。 (2)能够处理多位整数以及浮点数。 (3)具体测试数据...
Qt计算器的实现,支持四则运算,四则运算转换成后缀表达式计算,包含括号匹配算法,判断四则计算中是否有括号且是否左右括号成对出现,没有括号或者有成对出现的左右括号则返回值为真,括号不成对出现则返回值为假
功能得到了极大的提高!支持括号、小数、长数字、异常输入规避和判断。修复 V2版本中存在的...新增 输出后缀表达式;优化 输入输出数据范围;优化 在括号内输入单个数字的运算。程序可运行测试和使用。版本号:V3.01
在编写代码时我们有时候会碰到需要自己解析四则运算表达式的情况,本文简单的介绍使用JavaScript实现对简单四则运算表达式的解析。 一、熟悉概念 中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, ...
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算顺序的括号要...
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算顺序的括号要...
算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为简化,规定操作数只能为正整数,操作符为+、-*、/,用#表示结束。 算法输出:表达式运算结果。
要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,利用给定的算术符优先关系,实现对算数四则混合运算表达式的求值,并演示在求值过程中运算符栈、操作符栈、输入字符和主要操作的变化过程。
要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,利用给定的算术符优先关系,实现对算数四则混合运算表达式的求值,并演示在求值过程中运算符栈、操作符栈、输入字符和主要操作的变化过程。
将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算结果的括号要...
也可采用先转换成后缀表达式后再求值的方法(参看课件) 。 实现时需注意如下: ( 1)带小数点的数值生成 ( 理解整数数值的生成,小数部分的处理与之类似)。 ( 2)考虑负号的情况。负号与减号形式上一样,如何...
php实现一个简单的四则运算计算器(还不支持括号的优先级)。利用栈这种数据结构来计算表达式很赞。 这里可以使用栈的结构,由于php的数组“天然”就有栈的特性,这里直接就利用了数组。当然可以使用栈结构写,道理...
本源码利用栈实现了整数的加减乘除四则运算,支持多位数字的整数,支持括号。源码原理简单,重点是两个函数,一个函数是将中缀表达式转为后缀表达式,一个函数是对后缀表达式进行计算,求出结果。
(1)四则运算符 +, -, *, / (2)取正、取负 +, - (3)前后缀自增自减 ++, -- (对于变量后缀增与C++规则一致,对于数字后缀增则与前缀增一致) (4)幂运算 ^ (5)三角函数 sin/cos/tan Sin/Cos/Tan (大写使用弧度制,...
这是一个运行于vs2015的项目,代码也就200+行,实现的功能有基础的四则运算以及math里面cos,sin,pow函数的,有这几个函数为样本添加其他函数也很简单,代码实现简单,中缀转后缀,只用了一个栈,附加提醒,若是使用...
从键盘上输入一算术表达式,包括圆括号,计算出表达式的值。...(2)实现算术四则运算(+、-、*、/)和平方(^)运算,能处理双目运算符:+和-; (3)能将中缀算术表达式转换成后缀表达式并输出,并输出运算结果。