深圳著名设计网站大全,短视频推广引流,域名网站是什么,网页设计代码html模版文章目录中缀表达式转后缀表达式思路逆波兰表达式计算思路代码实现中缀表达式转后缀表达式思路
1、初始化两个栈#xff1a;运算符栈s1和储存中间结果的栈s2
2、从左至右扫描中缀表达式
3、遇到操作数时#xff0c;将其压入s2
4、遇到运算符时#xff0c;比较其与s1栈顶…
文章目录中缀表达式转后缀表达式思路逆波兰表达式计算思路代码实现中缀表达式转后缀表达式思路
1、初始化两个栈运算符栈s1和储存中间结果的栈s2
2、从左至右扫描中缀表达式
3、遇到操作数时将其压入s2
4、遇到运算符时比较其与s1栈顶运算符的优先级 ①如果s1为空或栈顶运算符为左括号“(” 则直接将此运算符入栈s1 ②否则若优先级比栈顶运算符的高也将运算符压入s1 ③否则将s1栈顶的运算符弹出并压入到s2中再次转到(4.1)
5、遇到括号时 ①如果是左括号“(”则直接压入s1 ②如果是右括号“)”则依次弹出s1栈顶的运算符并压入s2直到遇到左括号为 止此时将这一对括号丢弃
6、重复步骤2至5直到表达式结束
7、将s1中剩余的运算符依次弹出并压入s2
8、依次弹出s2中的元素并输出结果的逆序即为中缀表达式对应的后缀表达式 逆波兰表达式计算思路
(34)*5-6 对应的后缀表达式为 3 4 5 * 6 -针对后缀表达式求值步骤如下
1、从左至右扫描将3和4压入堆栈
2、遇到运算符弹出4和3 (4 为栈顶元素3为次顶元素)计算出34的值得 7再将7入栈
3、将5入栈
4、接下来是运算符弹出5和7计算出7535将35入栈
5、将6入栈
6、最后是 - 运算符弹出35和6计算35-629 由此得出最终结果 代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;/*** Author: Yeman* Date: 2021-10-27-21:59* Description:*/
public class PolandNotation {public static void main(String[] args) {//给一个中缀表达式String expression 1((23)*4)-10;//将中缀表达式放入ListListString infixList toInfixExpression(expression);//将中缀表达式对应的List转换为逆波兰表达式对应的ListListString suffixList parseSuffixExpression(infixList);//用逆波兰表达式后缀表达式进行计算int result calculate(suffixList);System.out.println(result);}//将中缀表达式放入List中public static ListString toInfixExpression(String expression){ListString ls new ArrayList();int i 0; //相当于一个指针用来遍历表达式String str; //用来拼接多位数char ch; //每遍历一个就存入chdo {//如果不是数,直接加入if ((ch expression.charAt(i)) 48 || (ch expression.charAt(i)) 57){ls.add(ch );i;}else {str ;while (i expression.length() (ch expression.charAt(i)) 48 (ch expression.charAt(i)) 57){str ch;i;}ls.add(str);}}while (i expression.length());return ls;}//将中缀表达式对应的List转成逆波兰表达式对应的Listpublic static ListString parseSuffixExpression(ListString infixList){StackString s1 new StackString(); //符号栈//由于操作中没有进行过pop可以使用ListString替换中间结果栈StackStringListString s2 new ArrayListString();for (String item : infixList){if (item.matches(\\d)){s2.add(item);}else if (item.equals(()){s1.push(item);}else if (item.equals())){while (!s1.peek().equals(()){s2.add(s1.pop());}s1.pop(); //将 ( pop出去}else {while (s1.size() ! 0 Operation.getValue(s1.peek()) Operation.getValue(item)){s2.add(s1.pop());}s1.push(item);}}while (s1.size() ! 0){s2.add(s1.pop());}return s2;}//逆波兰表达式计算public static int calculate(ListString expressionList){//创建一个栈StackString strings new StackString();//遍历列表for (String item : expressionList){if (item.matches(\\d)){ //匹配多位数strings.push(item);}else {int num2 Integer.parseInt(strings.pop());int num1 Integer.parseInt(strings.pop());String ch item;int res 0;switch (ch){case :res num1 num2;break;case -:res num1 - num2;break;case *:res num1 * num2;break;case /:res num1 / num2;break;default:throw new RuntimeException(运算符不正确);}strings.push(res );}}//for循环结束留在栈里的即为计算结果return Integer.parseInt(strings.pop());}
}//该类返回运算符优先级
class Operation{private static int ADD 1;private static int SUB 1;private static int MUL 2;private static int DIV 2;public static int getValue(String operation){int res 0;switch (operation){case :res ADD;break;case -:res SUB;break;case *:res MUL;break;case /:res DIV;break;default:System.out.println(运算符不正确);break;}return res;}
}
