精华内容
下载资源
问答
  • 本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...
  • 计算中缀表达式

    千次阅读 多人点赞 2018-05-06 15:42:10
    计算中缀表达式”可以称得上是一个特别经典的关于栈的算法题,几乎在所有数据结构教材中都会涉及,而且很多公司面试或者笔试的时候都会把这道题作为一个考察点。可以说,这是一道必须要掌握的算法题。中缀表达式、...

    “计算中缀表达式”可以称得上是一个特别经典的关于栈的算法题,几乎在所有数据结构教材中都会涉及,而且很多公司面试或者笔试的时候都会把这道题作为一个考察点。可以说,这是一道必须要掌握的算法题。中缀表达式、后缀表达式等概念在这里就不赘述了,让我们直奔主题。

    题目:输入一个中缀表达式,计算其结果。

    输入的前提假设:

    (1)只考虑+、-、*、/这四种运算符,中缀表达式中只有一种括号:();

    (2)输入的中缀表达式中只有整数,没有小数;

    (3)假定输入是合法的。

    很多文章或课本喜欢一步到位,直接讨论如何从中缀表达式计算结果。但对于初学者来说,跨度未免大了点。这里循序渐进,从易到难,先讨论如何将中缀表达式转化为后缀表达式,再讨论如何计算后缀表达式。最后在前面两步的基础上,讨论如何一步到位,直接计算中缀表达式的结果:

    一、如何将中缀表达式转化为后缀表达式

    在日常应用中,算术表达式中运算符总是出现在两个操作数之间,例如5*(7-2*3)+8/2,这种形式称为中缀表达式。计算一个中缀表达式需要知道运算符的优先级和结合性。乘除是高优先级,加减是低优先级,优先级相同时他们都是左结合的,也就是从左计算到右。有括号就要计算括号内的表达式。

    中缀表达式利于人的理解,但不便于计算机的处理。因此需要将中缀表达式转换成后缀表达式,以方便计算机处理。所谓后缀表达式就是将运算符放在运算数之后。后缀表达式也称为逆波兰表达式。

    比如:

    中缀表达式为:1+(2-3)*4+4/2

    对应后缀表达式为:1 2 3 - 4* + 4 2 / +

    如何将一个中缀表达式转化为后缀表达式?我们需要借助栈的力量,用它来存放运算符。算法流程如下:

    首先将各种运算符(包括括号)的优先级排列如下(数字越大,优先级越高):

    1:(

    2:+ -

    3:* /

    4:)

    对输入的中缀表达式从左到右遍历:

    1)如果遇到数字,直接添加到后缀表达式末尾;

    2)如果遇到运算符+、-、*、/:

    先判断栈是否为空。若是,则直接将此运算符压入栈。若不是,则查看当前栈顶元素。若栈顶元素优先级大于或等于此操作符级别,则弹出栈顶元素,将栈顶元素添加到后缀表达式中,并继续进行上述判断。如果不满足上述判断或者栈为空,将这个运算符入栈。要注意的是,经过上述步骤,这个运算符最终一定会入栈。

    3)如果遇到括号:

    如果是左括号,直接入栈。如果是右括号,弹出栈中第一个左括号前所有的操作符,并将左括号弹出。(右括号别入栈)。

    4)字符串遍历结束后,如果栈不为空,则弹出栈中所有元素,将它们添加到后缀表达式的末尾,直到栈为空。

    二、计算后缀表达式

    后缀表达式的计算就相当简单了。准备一个数字栈。从左到右扫描后缀表达式,如果是数字,放入数字栈。如果是符号,从数字栈中弹出两个数字,第一个取出的数字为右运算数,第二个为左运算数,进行运算。然后将结果放进数字栈中。如此反复,直到读完整个表达式后,留在数字栈中的那个数字就是最终结果。

    C++代码如下,要注意,下面的代码默认中缀表达式中所有数字都是整数,并且都在0到9之间。而且计算结果都是整数(比如5/2=2)。

    #include<iostream>
    #include<string>
    #include<stack>
    
    using namespace std;
    
    int getPriority(char ch)
    {
        //获取优先级
        if (ch == '(') return 1;
        else if (ch == '+' || ch == '-') return 2;
        else if (ch == '*' || ch == '/') return 3;
        else return 4;
    }
    
    string getPostfixExpression(string str)
    {
        //将中缀表达式转化为后缀表达式
        //默认输入是合法的
        stack<char> mystack;
        int size = str.size();
        int i = 0;
        char tmp;
        string res = "";
        while (i < size) {
            if (str[i] >= '0' && str[i] <= '9'){
                res.push_back(str[i]);
            }
            elseif (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
                if (mystack.empty()) {
                    mystack.push(str[i]);
                }
                else {
                    while (!mystack.empty()) {
                        tmp = mystack.top();
                        if (getPriority(tmp) >= getPriority(str[i])) {
                            //弹出栈顶元素
                            res.push_back(tmp);
                            mystack.pop();
                        }
                        else break;
                    }
                    mystack.push(str[i]);
                }
            }
            else {
                if(str[i]=='(') mystack.push(str[i]);
                else {
                    while (mystack.top() != '(') {
                        tmp = mystack.top();
                        res.push_back(tmp);
                        mystack.pop();
                    }
                    mystack.pop();
                }
            }
            i++;
        }
    
        //遍历完后,若栈非空,弹出所有元素
        while (!mystack.empty()) {
            tmp = mystack.top();
            res.push_back(tmp);
            mystack.pop();
        }
        return res;
    }
    
     
    
    int calculator(string str)
    {
        //计算后缀表达式的值,默认中缀表达式所有数字都是一位的,在0-9之间
        stack<int> mystack;
        int size = str.size();
        int num1, num2, num3;
        for (int i = 0; i < size; i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                mystack.push(str[i] - '0');
            }
            else {
                num2 = mystack.top();
                mystack.pop();
                num1 = mystack.top();
                mystack.pop();
                if (str[i] == '+') {
                    num3 = num1 + num2;
                }
                else if (str[i] == '-') {
                    num3 = num1 - num2;
                }
                else if (str[i] == '*') {
                    num3 = num1 * num2;
                }
                else if (str[i] == '/') {
                    num3 = num1 / num2;
                }
                mystack.push(num3);
            }
        }
        return mystack.top();
    }
    
     
    int main()
    {
        string str="1+(2-3)*4+4/2";
        cout <<"中缀表达式为:"<< endl << str << endl;
        string res = getPostfixExpression(str);
        cout <<"后缀表达式为:"<< endl << res << endl;
        int num_res = calculator(res);
        cout <<"计算结果:"<< endl << num_res << endl;
        system("pause");
        return 0;
    }

    三、直接计算中缀表达式

    其实将前面的两步结合起来,就可以得到直接计算的方法。准备一个数字栈和一个符号栈。

    从左到右遍历中缀表达式。如果遇到数字,入数字栈。

    如果遇到符号(四个运算符以及括号),跟前面的“中缀表达式转后缀表达式”过程一样,对符号栈进行处理。处理过程中,对每一个出栈的运算符:+ - * /,根据“计算后缀表达式”的方法,计算结果(跟数字栈配合)。

    如果遍历完中缀表达式后符号栈还非空,就继续出符号栈的运算符,计算,直到符号栈为空。最后数字栈剩下的数字就是结果。

    下面给出用C++实现“计算中缀表达式”的代码,里面考虑了“数字不止1位”,并且用浮点型来表示最终运算结果。要求中缀表达式中只能包含整数和运算符(不能包含小数),并且是合法的。

    #include<iostream>
    #include<string>
    #include<stack>
    
    using namespace std;
    
    int getPriority(char ch)
    {
    	//获取优先级
    	if (ch == '(') return 1;
    	else if (ch == '+' || ch == '-') return 2;
    	else if (ch == '*' || ch == '/') return 3;
    	else return 4;
    }
    
    void calculate(stack<double> &mystack, char operation)
    {
    	double num1, num2, num3;
    	num2 = mystack.top();
    	mystack.pop();
    	num1 = mystack.top();
    	mystack.pop();
    	if (operation == '+') {
    		num3 = num1 + num2;
    	}
    	else if (operation == '-') {
    		num3 = num1 - num2;
    	}
    	else if (operation == '*') {
    		num3 = num1 * num2;
    	}
    	else if (operation == '/') {
    		num3 = num1 / num2;
    	}
    
    	mystack.push(num3);
    }
    
    double calculator(string str)
    {
    	//计算中缀表达式,默认输入是合法的
    	stack<double> mystack_number;
    	stack<char> mystack_operation;
    	int i = 0, j;
    	int size = str.size();
    	char tmp_operation;
    	string tmp_num;
    	while (i < size) {
    		if (str[i] >= '0' && str[i] <= '9') {
    			j = i;
    			while (j < size && str[j] >= '0' && str[j] <= '9') { j++; }
    			tmp_num = str.substr(i, j - i);
    			mystack_number.push(atoi(tmp_num.c_str()));
    			i = j;
    		}
    		else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
    			if (mystack_operation.empty()) {
    				mystack_operation.push(str[i]);
    			}
    			else {
    				while (!mystack_operation.empty()) {
    					tmp_operation = mystack_operation.top();
    					if (getPriority(tmp_operation) >= getPriority(str[i])) {
    						//计算
    						calculate(mystack_number, tmp_operation);
    						mystack_operation.pop();
    					}
    					else break;
    				}
    				mystack_operation.push(str[i]);
    			}
    			i++;
    		}
    		else {
    			if (str[i] == '(') mystack_operation.push(str[i]);
    			else {
    				while (mystack_operation.top() != '(') {
    					tmp_operation = mystack_operation.top();
    					//计算
    					calculate(mystack_number, tmp_operation);
    					mystack_operation.pop();
    				}
    				mystack_operation.pop();
    			}
    			i++;
    		}
    
    	}
    	//遍历完后,若栈非空,弹出所有元素
    	while (!mystack_operation.empty()) {
    		tmp_operation = mystack_operation.top();
    		//计算
    		calculate(mystack_number, tmp_operation);
    		mystack_operation.pop();
    	}
    	return mystack_number.top();
    }
    
    int main()
    {
    	string str = "1+(2-3)*4+10/2+2*2+2+2/5";
    	cout << "中缀表达式为:" << endl << str << endl;
    	double num_res = calculator(str);
    	cout << "计算结果:" << endl << num_res << endl;
    	system("pause");
    	return 0;
    }
    

    相信通过这篇文章,大家对这个问题会有所了解。

    给出一道思考题:如果加入乘方'^',应该如何处理?要注意,乘方运算是右结合的。

    其实很简单。只有两处修改:

    1)将乘方添加到优先级中:

    1:(

    2:+ -

    3:* /

    4:^

    5:)

    2)在读中缀表达式的时候,如果读到乘方^,就将它放进符号栈中。因为乘方的优先级是最高的,而且是右结合的,所以无论它前面出现的是什么运算,这些运算都不能执行。而且它本身能否执行也是不知道的,因此只能进栈。

    大家自己试试吧~要记住,学习编程,动手去写代码永远是第一位的。

    【参考资料】

    [1]https://blog.csdn.net/sinat_36118270/article/details/70257547

    [2]翁惠玉, 俞勇. 数据结构:思想与实现[M]. 高等教育出版社, 2009.

    展开全文
  • 中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的表达式值,比较两个计算结果,判断转换正确性和计算正确性。 ·编程 (1)读入中缀表达式,表达式的数据可以是实型、整型; (2)转换为后缀表达式...
  • 中缀表达式转后缀表达式并计算 中缀表达式 后缀表达式

    中缀表达式转后缀表达式并计算

    中缀表达式就是我们正常工作中写的表达式,如 a+(b-c)d ,编译系统将中缀表达式改写 abc-d+ ,这种运算符在操作数后面称为后缀表达式(也称逆波兰表达式)。

    题目:输入一个中缀表达式,计算其结果。
    输入的前提假设:
    (1)只考虑+、-、*、/这四种运算符,中缀表达式中只有一种括号:();
    (2)输入的中缀表达式中只有整数,没有小数;
    (3)假定输入是合法的。

    案例:1+ (2-3) * 4 + 6/3
    提示:利用栈的“记忆”,符号都推入栈即可!
    注意:计算一个中缀表达式需要知道运算符的优先级和结合性。乘除是高优先级,加减是低优先级,优先级相同时他们都是左结合的,也就是从左计算到右。有括号就要计算括号内的表达式。

    中缀表达式转换为后缀表达式

    利用栈来实现转换

    转换过程需要用到栈,这里使用两个栈stack 栈用来存放运算符post 栈用来存放最后的后缀表达式。具体规则如下:
    从左到右扫描中缀表达式:
    若是操作数,直接存入 post 栈;
    若是运算符:
    (1)该运算符是左括号 ( , 则直接存入 stack 栈。
    (2)该运算符是右括号 ),则将 stack 栈中 ( 前的所有运算符出栈,存入 post 栈。
    (3)若该运算符为非括号,则将该运算符和 stack 栈顶运算符作比较:若高于栈顶运算符,则直接存入 stack 栈,否则将栈顶运算符出栈(从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止),存入 post 栈。
    (4)当扫描完后,stack 栈中还有运算符时,则将所有运算符出栈,存入 post 栈。
    例子:中缀表达式 a + b * c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f + g * +。
    具体过程如下:

    扫描stack栈post栈
    aa
    a++a
    a+b+ab
    a+b*+*ab
    a+b*c+*abc
    a+b*c++abc*+
    a+b*c+(+(abc*+
    a+b*c+(d+(abc*+d
    a+bc+(d+(*abc*+d
    a+bc+(de+(*abc*+de
    a+bc+(de++(+abc*+de*
    a+bc+(de+f+(+abc*+de*f
    a+bc+(de+f)+abc*+de*f+
    a+bc+(de+f)*+*abc*+de*f+
    a+bc+(de+f)*g+*abc*+de*f+g
    a+bc+(de+f)*g#abc*+def+g+

    注意:表格中第6步,读到+,因为栈顶元素的优先级高,所以出栈,栈中下一个元素+优先级与读到的操作符+一样,所以也要弹出。然后再将读到的+压入栈中。第13步,读到),则直接将栈中元素弹出直到遇到(为止。这里左括号前只有一个操作符+被弹出。

    因此,对于案例中的表达式,将其转换为后缀表达式后的结果为123-4*+63/+

    另外,还有其他方法可以实现中缀表达式转后缀表达式

    利用语法树

    先将中缀表达式用二叉树表示出来,再后序遍历该二叉树,就得到其相应的后缀表达式。

    加括号法

    加括号法先将中缀表达式每步要计算的表达式加上括号,然后将每个运算符移到其所在括号的外面,最后,从左到右去掉括号后就是后缀表达式。
    *示例: a+(b-c)d
    加括号后: (a+((b-c)d))
    移运算符: (a((bc)-d)*)+
    去括号 abc-d+

    计算后缀表达式

    后缀表达式的计算就相当简单了。准备一个数字栈。从左到右扫描后缀表达式,如果是数字,放入数字栈。如果是符号,从数字栈中弹出两个数字,第一个取出的数字为右运算数,第二个为左运算数,进行运算。然后将结果放进数字栈中。如此反复,直到读完整个表达式后,留在数字栈中的那个数字就是最终结果。
    例如:假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下:

    • 遍历表达式,遇到数字首先放入栈,此时栈如下 6 5 2 3
    • 接着读到+,则弹出3和2,执行2+3,将结果5压栈 6 5 5
    • 读到8,压栈 6 5 5 8
    • 读到 , 弹出8和5,执行58,将结果40压栈 6 5 40
    • 读到 +,弹出40和5,执行5+40,将结果45压栈 6 45
    • 读到 3,压栈 6 45 3
    • 读到 +,弹出3和45,执行45+3,将结果48压栈 6 48
    • 读到 ,弹出48和6,执行648,将结果288压栈 288

    最后结果288
    代码如下:

    package DataStructure;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.Stack;
    
    /**
     * 中缀表达式转后缀表达式并计算
     */
    public class NifixExpression {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNextLine()) {
                String exp = sc.nextLine();
                // 将中缀表达式转为List形式
                List<String> nifixExpression = nifix2List(exp);
                System.out.println("NifixExpression = " + nifixExpression);
                List<String> postfixExpression = nifix2postfix(nifixExpression);
                System.out.println("postfixExpression = " + postfixExpression);
                // 计算后缀表达式的值
                int reslut = calculate(postfixExpression);
                System.out.println(exp + " = " + reslut);
            }
        }
    
        /**
         * 根据后缀表达式计算结果
         *
         * @param postfixExpression
         * @return
         */
        private static int calculate(List<String> postfixExpression) {
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < postfixExpression.size(); i++) {
                String item = postfixExpression.get(i);
                if (isNumber(item)) {
                    //是数字
                    stack.push(Integer.parseInt(item));
                } else {
                    //是操作符,取出栈顶两个元素
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    int res = 0;
                    switch (item) {
                        case "+":
                            res = num1 + num2;
                            break;
                        case "-":
                            res = num1 - num2;
                            break;
                        case "*":
                            res = num1 * num2;
                            break;
                        case "/":
                            res = num1 / num2;
                            break;
                        default:
                            throw new RuntimeException("运算符错误!");
                    }
                    stack.push(res);
                }
            }
            return stack.pop();
        }
    
        /**
         * 将表达式转为List格式
         *
         * @param exp
         * @return
         */
        private static List<String> nifix2List(String exp) {
            int index = 0;
            List<String> list = new ArrayList<>();
            do {
                char chr = exp.charAt(index);
                // 从48到57对应ASCII的0到9数字
                if (chr <= 47 || chr >= 58) { //是操作符, 直接加入到list中
                    index++;
                    list.add(chr + "");
                } else if (chr > 47 && chr < 58) { //是数字,需要判断是否是多位
                    String str = "";
                    while (index < exp.length() && exp.charAt(index) > 47 && exp.charAt(index) < 58) {
                        str += exp.charAt(index);
                        index++;
                    }
                    list.add(str);
                }
            } while (index < exp.length());
            return list;
        }
    
        private static List<String> nifix2postfix(List<String> exp) {
            // 创建一个栈用来保存操作符
            Stack<String> operatorStack = new Stack<>();
            // 创建一个List用来保存后缀表达式
            List<String> sufffixList = new ArrayList<>();
            for (String item : exp) {
                //得到数或操作符
                if (isOperator(item)) {
                    //是操作符,判断操作符栈是否为空
                    if (operatorStack.isEmpty() || "(".equals(operatorStack.peek()) || priority(item) > priority(operatorStack.peek())) {
                        //为空或者栈顶元素为左括号或者当前操作符大于栈顶操作符的优先级则直接压栈
                        operatorStack.push(item);
                    } else {
                        //否则将栈中元素出栈入队,直到遇到大于当前操作符的优先级或者遇到左括号
                        while (!operatorStack.isEmpty() && !"(".equals(operatorStack.peek())) {
                            if (priority(item) <= priority(operatorStack.peek())) {
                                sufffixList.add(operatorStack.pop());
                            }
                        }
                        // 当前操作符压栈
                        operatorStack.push(item);
                    }
                } else if ((isNumber(item))) {
                    //是数字则直接入队
                    sufffixList.add(item);
                } else if ("(".equals(item)) {
                    //是左括号,直接压栈
                    operatorStack.push(item);
                } else if (")".equals(item)) {
                    //是右括号,则将栈中元素弹出,直到遇到左括号,左括号出栈,但不入队
                    while (!operatorStack.isEmpty()) {
                        if ("(".equals(operatorStack.peek())) {
                            operatorStack.pop();
                            break;
                        } else {
                            sufffixList.add(operatorStack.pop());
                        }
                    }
                } else {
                    throw new RuntimeException("有非法字符!");
                }
            }
            //循环完毕,如果操作符栈中元素不为空,将栈中元素出栈入队
            while (!operatorStack.isEmpty()) {
                sufffixList.add(operatorStack.pop());
            }
            return sufffixList;
        }
    
        /**
         * 判断是否为数字
         *
         * @param item
         * @return
         */
        private static boolean isNumber(String item) {
            return item.matches("\\d+");
        }
    
        /**
         * 获取操作符的运算优先级
         *
         * @param item
         * @return
         */
        private static int priority(String item) {
            if (item.equals("*") || item.equals("/")) {
                return 1;
            } else if (item.equals("+") || item.equals("-")) {
                return 0;
            }
            return -1;
        }
    
        /**
         * 判断是否为操作符
         *
         * @param item
         * @return
         */
        private static boolean isOperator(String item) {
            return item.equals("+") || item.equals("-") || item.equals("*") || item.equals("/");
        }
    }
    
    
    展开全文
  • 利用后缀表达式计算中缀表达式的值.数据结构 花费了我2周的时间才完成的 数据结构 c语言 MFC,是用MFC做的,,该程序功能强大,健壮性很强,对于错误输入有提示,程序完全正确,解压既可以运行
  • c++计算中缀表达式

    2021-03-23 19:31:38
    输入中缀表达式的字符串,可能存在括号,输出计算结果。 除法是向0取整,仅包含加减乘除四则运算。 #include <iostream> #include <stack> #include <unordered_map> using namespace std; ...

    输入中缀表达式的字符串,可能存在括号,输出计算结果。
    除法是向0取整,仅包含加减乘除四则运算。

    #include <iostream>
    #include <stack>
    #include <unordered_map>
    
    using namespace std;
    
    stack<char> op; //存运算符
    stack<int> num; //存运算数
    unordered_map<char, int> pr={{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //定义优先级
    
    void eval() //计算最后两个数
    {
        int b = num.top();
        num.pop();
        int a = num.top();
        num.pop();
        char c = op.top();
        op.pop();
        int x;
        if (c == '*') x = a * b;
        else if (c == '/') x = a / b;
        else if (c == '+') x = a + b;
        else x = a - b;
        num.push(x);
    }
    
    int main()
    {
        string s;
        cin >> s;
        for (int i = 0; i < s.size(); i ++ )
        {
            char c = s[i];
            if (isdigit(c)) //将数压入栈
            {
                int x = 0;
                int j = i;
                while (j < s.size() && isdigit(s[j]))
                {
                    x = x * 10 + s[j] - '0';
                    j ++ ;
                }
                num.push(x);
                i = j - 1;
            }
            else if (c == '(') op.push(c);
            else if (c == ')')
            {
                while (op.top() != '(') eval();
                op.pop();
            }
            else
            {
    	        //当前一个运算符优先级较高时进行计算
                while (op.size() && pr[op.top()] >= pr[c]) eval();        
                op.push(c);
            }
        }
        
        while (op.size()) eval(); //可能还没算完
        cout << num.top(); //计算结果是栈顶元素
        return 0;
    }
    
    展开全文
  • Java栈计算中缀表达式 一、思路分析 给出一个中缀表达式:“3+2*6-2” 从左到右依次扫描字符串,当前字符为数字时,直接进数字栈;当前字符为运算符时,若当前运算符栈为空,则直接入栈,否则拿当前运算符与运算符...

    Java栈计算中缀表达式

    一、思路分析

    1. 给出一个中缀表达式:“3+2*6-2”
    2. 从左到右依次扫描字符串,当前字符为数字时,直接进数字栈;当前字符为运算符时,若当前运算符栈为空,则直接入栈,否则拿当前运算符与运算符栈顶运算符比较优先级,若当前运算符优先级>=栈顶运算符优先级,则直接入栈,若当前运算符优先级<栈顶运算符优先级,则从数字栈中弹出两个数据且从运算符栈中弹出栈顶运算符,计算结果;将计算结果入数字栈,当前运算符入运算符栈。
    3. 直到字符串扫描结束,如果运算符栈不为空,则从数字栈中弹出两个数据且从运算符栈中弹出栈顶运算符,计算结果;将计算结果入数字栈,当前运算符入运算符栈。
    4. 此时,数字栈中剩余的一个数就是表达式的结果。

    二、代码如下:

    package com.stack;
    
    public class Calculator {
    	public static void main(String[] args) {
    		String expression = "30+2*6/2";
    		// 创建两个栈,一个存放数字,一个存放运算符
    		ArrayStack2 numStack = new ArrayStack2(10);
    		ArrayStack2 operStack = new ArrayStack2(10);
    		// 定义需要的相关变量
    		int index = 0; // 从0开始扫描
    		int num1 = 0;
    		int num2 = 0;
    		int oper = 0;
    		int res = 0;
    		char ch = ' '; // 用于保存扫描到的字符
    		String keepNum = ""; // 用于拼接多位数
    		while (true) {
    			ch = expression.charAt(index);
    			if (ArrayStack2.isOper(ch)) { // 如果是运算符
    				// 判断当前运算符栈为空
    				if (operStack.isEmpty()) {
    					operStack.push(ch); // 直接入栈
    				} else { // 运算符栈不为空
    					// 判断优先级,如果当前运算符优先级小于栈顶运算符优先级
    					if (ArrayStack2.priority(ch) <= ArrayStack2.priority(operStack.peek())) {
    						num1 = numStack.pop();
    						num2 = numStack.pop();
    						oper = operStack.pop();
    						res = ArrayStack2.calculate(num1, num2, oper);
    						// 将计算结果入栈
    						numStack.push(res);
    						// 将当前运算符入栈
    						operStack.push(ch);
    					} else { // 当前运算符优先级大于栈顶运算符优先级
    						operStack.push(ch); // 直接入栈
    					}
    				}
    			} else { // 是数字
    				keepNum += ch;
    				// 判断是不是多位数
    				// 1、下一位字符还是数字,则判定为多位数,用字符串进行拼接
    				// 2、下一位字符是运算符,则判定为个位数,直接入栈
    				if (index == expression.length() - 1) { // 扫描到最后一个字符
    					numStack.push(Integer.parseInt(keepNum));
    				} else { // 没有扫描到最后一个字符
    					if (ArrayStack2.isOper(expression.charAt(index + 1))) {
    						numStack.push(Integer.parseInt(keepNum));
    						keepNum = "";
    					}
    				}
    			}
    			index++;
    			// 判断是否扫描到结束位置
    			if (index >= expression.length()) {
    				break;
    			}
    		}
    
    		// 扫描结束后,从数字栈、运算符栈中弹出,最后一个值就是计算结果
    		while (true) {
    			if (operStack.isEmpty()) {
    				break;
    			}
    			num1 = numStack.pop();
    			num2 = numStack.pop();
    			oper = operStack.pop();
    			res = ArrayStack2.calculate(num1, num2, oper);
    			// 将计算结果入栈
    			numStack.push(res);
    		}
    		System.out.println("结果是:" + numStack.pop());
    	}
    }
    
    class ArrayStack2 {
    	private int maxSize;// 栈的大小
    	private int[] stack;// 存储数据的数组
    	private int top = -1;// 栈顶
    
    	public ArrayStack2(int maxSize) {
    		this.maxSize = maxSize;
    		stack = new int[maxSize];
    	}
    
    	// 返回栈顶的值
    	public int peek() {
    		return stack[top];
    	}
    
    	/**
    	 * 是否栈满
    	 * 
    	 * @return true/false
    	 */
    	public boolean isFull() {
    		return top == maxSize - 1;
    	}
    
    	/**
    	 * 是否栈空
    	 * 
    	 * @return true/false
    	 */
    	public boolean isEmpty() {
    		return top == -1;
    	}
    
    	/**
    	 * 将element入栈
    	 * 
    	 * @param element
    	 */
    	public void push(int element) {
    		if (isFull()) {
    			throw new RuntimeException("栈满!");
    		} else {
    			top++;
    			stack[top] = element;
    		}
    	}
    
    	/**
    	 * 出栈
    	 * 
    	 * @return element
    	 */
    	public int pop() {
    		if (isEmpty()) {
    			throw new RuntimeException("栈空!");
    		} else {
    			int value = stack[top];
    			top--;
    			return value;
    		}
    	}
    
    	/**
    	 * 遍历
    	 */
    	public void show() {
    		System.out.println("当前栈的情况如下:");
    		for (int i = 0; i <= top; i++) {
    			System.out.printf("%d\t", stack[i]);
    		}
    		System.out.println();
    	}
    
    	// 返回符号的优先级
    	public static int priority(int oper) {
    		if (oper == '*' || oper == '/') {
    			return 1;
    		} else if (oper == '+' || oper == '-') {
    			return 0;
    		} else {
    			return -1;
    		}
    	}
    
    	// 判断当前字符是不是运算符
    	public static boolean isOper(int ch) {
    		return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    	}
    
    	// 计算
    	public static int calculate(int num1, int num2, int oper) {
    		int res = 0;
    		switch (oper) {
    		case '+':
    			res = num1 + num2;
    			break;
    		case '-':
    			res = num2 - num1;
    			break;
    		case '*':
    			res = num1 * num2;
    			break;
    		case '/':
    			res = num2 / num1;
    			break;
    		default:
    			break;
    		}
    		return res;
    	}
    }
    
    展开全文
  • JAVA用栈计算中缀表达式(详解)

    千次阅读 2020-09-27 16:17:13
    今天这一篇就是用栈这个数据结构,来解决中缀表达式计算。 也就是数学表达式的计算。 题目也很简单: 假如有个字符串表达式(“5+2*5-4/1”),用栈来计算这个表达式的值。 OKK,现在我们来分析一下怎么来做。然后...
  • java代码实现中缀表达式转后缀表达式,并计算结果
  • 本关任务要求通过实现函数double ComputeInfix(char* s)来计算中缀表达式。 相关知识 中缀表达式的计算需要用到栈。关于链接存储的栈,其中已实现了如下操作: 创建栈:创建一个链式栈。具体操作函数定义如下:...
  • 样例输入: (1+2)*(9-6) 样例输出: result = 9.000000 基本思路: 1、遇到数字进栈; 2、遇到( 进栈; 3、遇到+或-,判断栈顶元素是不是(,是就进栈,不是就计算,确保...//计算中缀表达式 { // 请在此添加代码
  • c语言用栈实现计算中缀表达式

    千次阅读 2020-04-06 12:48:15
    c语言用栈实现计算中缀表达式 解决这个问题需要两步: 将中缀式换成后缀式(后缀式更利于写算法) 计算后缀式。 因为还要满足多位数和小数,所以用了字符串。 typedef struct { char c[100]; }X; typedef struct ...
  • 本关任务要求通过实现函数double ComputeInfix(char* s)来计算中缀表达式。 相关知识 中缀表达式的计算需要用到栈。关于链接存储的栈,其中已实现了如下操作: 创建栈: 创建一个链式栈。具体操作函数定义如下: ...
  • 给定一个中缀表达式,如果合法那么求出它的值,否则返回错误信息。 首先要将中缀表达式转换为后缀表达式(逆波兰表达式) 这里的输入限定为:除操作符外均为小写字母,假设输入合法的中缀表达式 思想:从左到右...
  • C++中缀表达式计算

    2015-10-23 19:32:47
    利用c语言写的中缀表达式,主要数据结构是栈。
  • 计算中缀表达式的值

    2020-02-24 11:17:21
    分两步,一是将中缀转后缀,而是计算后缀表达式。 #include <iostream> #include <cstdio> #include <string> #include <stack> #include <queue> #include <map> using nam...
  • 递归计算中缀表达式

    万次阅读 2019-04-12 13:56:13
    递归计算中缀表达式 计算一个四则运算的中缀表达式 如: Input: 6+12*(15*5+2-4)+5/(1+2) Output: 883.667 #include <iostream> using namespace std; float value(int priorty = 2) { float result = ...
  • //用于指向字符串(中缀表达式)的指针 //声明两个栈,一个float型,一个char型 //表达式中操作数存在一个栈内,运算符存入一个栈内 //top1,top2用于指向两个栈的栈顶 float s1[maxSize];int top1=-1; char ...
  • c语言中缀表达式计算

    2015-01-03 18:15:23
    利用c语言写的中缀表达式,主要数据结构是栈。
  • C/C++ 语言实现利用栈计算中缀表达式的值
  • 本资源是数据结构中利用顺序栈计算中缀表达式的一个C++代码,仅供参考,不足之处请大神们指正.
  • 从键盘输入中缀表达式,建立操作数与运算符堆栈,计算并输出表达式的求值结果。 基本要求:实现 +, -, *, /四个二元运算符以及(); 操作数范围为0至9。 提高要求:实现+, -两个一元运算符(即正、负号); 操作...
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • 数据结构-用栈计算中缀表达式(过程解析)

    千次阅读 多人点赞 2019-04-29 12:21:41
    = t 栈顶(优先级),则t 出栈一个元素,s 出栈2个元素并计算后将计算后的值入栈s,直到t栈顶优先级大于c 运算符c 为( ,则入栈,遇到) 时出栈( ) 之间的所有运算符 解析 从左向右扫描: s、t初始状...
  • 计算中缀表达式的值,例如:输入2*(3+5)+7/1-4,输出19 e. 中缀表达式变换为后缀表达式,例如:输入2*(3+5)+7/1-4,输出235+*71/+4- 用例: 假如输入为:2*(3+5)+7/1-4 则输出为: 输入一个中缀表达式: 表达式计算...
  • 四川大学计算机学院-数据结构与算法分析高分实验报告-利用后缀表达式计算中缀表达式的值.rar 都是自己非常认真完成的,每一个要点都实现到位,还额外实现了创新内容。 最后得到的分数也很好

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,641
精华内容 6,256
关键字:

计算中缀表达式