精华内容
下载资源
问答
  • 计算后缀表达式

    千次阅读 2018-08-15 20:02:24
    一、通过栈把中缀表达式转换为后缀表达式的步骤: 从左至右扫描中缀表达式, if(遇到数字){  加入后缀表达式 }else if(遇到 ‘(’ ){  入栈 }else if(遇到 ‘)’ ){  依次将栈中元素出栈并加入到后缀...

    一、通过栈把中缀表达式转换为后缀表达式的步骤:

    从左至右扫描中缀表达式,

    if(遇到数字){

        加入后缀表达式

    }else if(遇到 ‘(’ ){

        入栈

    }else if(遇到 ‘)’ ){

        依次将栈中元素出栈并加入到后缀表达式,直到遇到 ‘(’ 并将其从栈中删除

    }else if(遇到运算符op){

        if(栈顶元是 ‘(’ ){

            op入栈

        }else{

            if(高于栈顶运算符优先级){

                op入栈

            }else{

                依次将比op优先级高的和相等的运算符出栈加入到后缀表达式,

                直到遇到比op优先级低的运算符或左括号(低优先级运算符或左括号不出栈)或栈空为止

                op入栈

            }

        }

    }

    扫描完毕后栈中所有剩下的运算符出栈加入到后缀表达式

     

    二、通过后缀表达式计算表达式的值的步骤:

    顺序扫描表达式的每一项

    if(遇到操作数){

        入栈

    }else if(遇到操作符op){

        连续从栈中退出两个操作数Y和X(先出栈的为Y)

        将 X<op>Y的结果入栈

    }

    表达式扫描完毕后栈顶元素就是所求的结果

     

    三、计算后缀表达式的代码:

    #include <cassert>
    #include <iostream>
    #include <string>
    #include <vector>
    #include <stack>
    #include <map>
    using std::cout;
    using std::endl;
    using std::string;
    using std::vector;
    using std::stack;
    using std::map;
    class CalcExpress
    {
    	private:
    		enum factorTag{LB,RB,NUM,ADD=10,MINU,MULT = 20,DIV,UNARY=30};//()1 +-*/-//类型标记
    		//enum设置默认值10,20是为了区分+- */ -(负号),使得相差较大,便于区别
    		static map<char,enum factorTag> tagPair;//mapTag
    		typedef std::pair<string,enum factorTag> ExpType;//类型,如<'+',ADD>
    		static bool isError;//出错标识
    		//------------TEST
    	public:
    
    		static void display(const string & s,const vector<ExpType> & x){
    			cout<<s<<":"<<endl;
    			for(auto & elem:x){
    				cout<<elem.first<<"\t\t"<<elem.second<<endl;
    			}
    			cout<<endl;
    		}
    
    		static void display(const vector<ExpType> & x){
    			cout<<"----"<<endl;
    			for(auto & elem:x){
    				cout<<elem.first<<"\t\t"<<elem.second<<endl;
    			}
    			cout<<endl;
    		}
    
    		static void test(){
    			string s1("(1+2*-35)/34");
    			string s2("-1/2-10-(-333+1)");
    			string s3("-(153+2*3)/4");
    			string s4("(1+2)*3");
    			string s5 = "1--2*3/(2/-3-5)";
    			vector<ExpType> vecTest;
    			//strToExpress(s1,vecTest);display(s1,vecTest);
    			//strToExpress(s2,vecTest);display(s2,vecTest);
    			//strToExpress(s3,vecTest);display(s3,vecTest);
    			vector<ExpType> inExp,postExp;
    			string s = s5;
    			strToExpress(s,inExp);
    			display(s,inExp);
    			inExpToPostExp(inExp,postExp);
    			display(postExp);
    			double ret = calcExpressProcess(postExp);
    			if(!isError){
    				cout<<"result = "<<ret<<endl;
    			}else{
    				cout<<"process error"<<endl;
    			}
    		}
    		//------------TEST
    
    	public:
    		static double calcExpress(const char * str){
    			if(!str){
    				isError = true;
    				return 0;
    			}
    			string cppString(str);
    			//判断字符串是否是合法表达式
    			if(!isValidExpress(cppString)){
    				isError = true;
    				return 0;
    			}
    			double ret = 0;
    			isError = false;
    			vector<ExpType> express;//数组保存每一个项
    			strToExpress(cppString,express);//将表达式的每一项存到数组
    			ret = calcExpressProcess(express);
    			return ret;
    		}
    	private:
    
    
    		static bool isValidExpress(const string & cppString){//判断表达式是否合法
    			//待补充完整
    			return true;
    		}
    
    		static void strToExpress(const string & cppString,vector<ExpType> & express){//将string转成ExpType表达式类型
    			//(1+2*-3)/34
    			//-1/2-1-(-3+1)
    			//-(1+2*3)/4
    			express.clear();
    			size_t preIdx = 0;
    			size_t size = cppString.size(); 
    			enum factorTag flag;
    			for(size_t i = 0;i<size;++i){
    				preIdx = i;//k记录数字的第一个位置
    				if(cppString[i] == '-'){
    					if(i==0 || (cppString[i-1] != ')' && !::isdigit(cppString[i-1]))){
    						//-作为负号的场景:前面不是数字或者)
    						flag = UNARY;
    					}else{//减号
    						flag = MINU;
    					}
    				}else if(isdigit(cppString[i])){//数字
    					while(i<size && isdigit(cppString[i])){
    						++i;	
    					}
    					--i;
    					flag = NUM;
    				}else{
    					switch(cppString[i]){
    						case '+':
    							flag = ADD;break;
    						case '*':
    							flag = MULT;break;
    						case '/':
    							flag = DIV;break;
    						case '(':
    							flag = LB;break;	
    						case ')':
    							flag = RB;break;
    						default:
    							isError = true;
    							cout<<"express ERROR"<<endl;
    							return;
    					}
    				}
    				express.push_back(ExpType(string(cppString,preIdx,i-preIdx+1),flag));
    			}
    		}
    
    
    		static void inExpToPostExp(const vector<ExpType> & inExp,vector<ExpType> & postExp){
    			postExp.clear();
    			postExp.reserve(inExp.size());
    			stack<ExpType> stk;//栈
    			for(auto & inTerm:inExp){
    				if(inTerm.second == NUM){//数值
    					postExp.push_back(inTerm);
    				}else if(inTerm.second == RB){//右括号
    					while(!stk.empty()){
    						if(stk.top().second == LB){//左括号
    							stk.pop();
    							break;
    						}else{
    							postExp.push_back(stk.top());
    							stk.pop();
    						}
    					}
    				}else if(inTerm.second == LB){//左括号
    					stk.push(inTerm);
    				}else{//运算符
    					while(
    							!stk.empty() && \
    							(\
    							 (inTerm.second <= stk.top().second) || ((inTerm.second - stk.top().second) == 1) \
    							)\
    						 ){//如果栈顶是高优先级或平级运算符
    						postExp.push_back(stk.top());
    						stk.pop();
    					}
    					stk.push(inTerm);
    				}
    			}
    			while(!stk.empty()){
    				postExp.push_back(stk.top());
    				stk.pop();
    			}
    		}
    
    		static double calcExpressProcess(const vector<ExpType> & postExp){
    			stack<double> calcStk;//栈用于记录中间过程的值
    			for(auto & postTerm:postExp){
    				if(postTerm.second == NUM){//数值
    					calcStk.push(stod(postTerm.first));
    				}else{//运算符
    					if(postTerm.second == UNARY){//负号
    						auto & val = calcStk.top();
    						val = -val;
    					}else{//其他双目运算符
    						double num2 = calcStk.top();
    						calcStk.pop();
    						double num1 = calcStk.top();
    						calcStk.pop();
    						if(postTerm.second == DIV){//判断是否发生除零
    							const double limit = 0.000000001;
    							if(num2 >= -1*limit && num2 <= limit){//num2为0
    								isError = true;
    								cout<<"error,Divide zero"<<endl;
    								abort();
    							}
    						}
    						double val = 0;
    						switch(postTerm.second){
    							case ADD:
    								val = num1 + num2;break;
    							case MINU:
    								val = num1 - num2;break;
    							case MULT:
    								val = num1 * num2;break;
    							case DIV:
    								val = num1*1.0 / num2;break;
    							default:
    								isError = true;
    								cout<<"express ERROR"<<endl;
    								return 0;
    						}
    						calcStk.push(val);
    					}
    				}
    			}
    			if(calcStk.size() != 1){//最后栈中剩下的数就是结果
    				isError = true;
    				cout<<"express ERROR"<<endl;
    				return 0;
    			}
    			return calcStk.top();
    		}
    
    };
    bool CalcExpress::isError = false;
    int main(){
    	CalcExpress::test();
    	return 0;
    }
    

     

    展开全文
  • 一个算术表达式是由操作数(operand)、运算符(operator)和括号组成的。...用户可选择需要进行的操纵,包括后缀表达式计算,中缀表达式转为后缀表达式,清屏和退出,界面清晰,操作简便,且有足够的输入合法性检验
  • 而栈可以把一般的中缀表达式变成后缀表达式,并且计算后缀表达式得出结果,因此此应用在计算器中非常常用。 二、中缀表达式转换成后缀表达式 此方法需要遵循几个规则: (1)如果读入操作数,则
    一、后缀表达式介绍
    后缀表达式的特点就是计算机运算非常方便,需要用到栈;计算机处理过程只需要顺序读入,如果遇到数字,则放入栈中,如果是运算符,则将两个栈中数字取出进行运算;比如1+2的后缀表达式为1 2 +;而栈可以把一般的中缀表达式变成后缀表达式,并且计算后缀表达式得出结果,因此此应用在计算器中非常常用。

    二、中缀表达式转换成后缀表达式

    此方法需要遵循几个规则:
    (1)如果读入操作数,则直接放入输出字符串;
    (2)如果读入一般运算符如+-*/,则放入堆栈,但是放入堆栈之前必须要检查栈顶,并确定栈顶运算符的优先级比放入的运算符的优先级低;如果放入的优先级较低,则需要将栈顶的运算符放入输出字符串;
    (3)如果读入(,因为左括号优先级最高,因此放入栈中,但是注意,当左括号放入栈中后,则优先级最低;
    (4)如果读入),则将栈中运算符取出放入输出字符串,直到取出(为止,注意:()不输出到输出字符串;
    (5)顺序读完表达式,如果栈中还有操作符,则弹出,并放入输出字符串;

    (如果用表达式创建一个树,叶子节点全是操作数,内部节点全是操作符,后续遍历这棵树,便可得到后缀表达式。)

    三、计算后缀表达式

    规则如下:
    (1)如果是操作数,则放入栈中;
    (2)如果是操作符,则取出栈中两个操作数,进行运算后,将结果放入栈中;
    (3)直到最后栈中只有一个元素,此元素就是计算结果;
     
    四、代码
    以下代码是计算器的辅助代码,通过此代码可以快速进行计算。
    输入: 四则运算(支持括号)
    输出:结果字符串

    package org.xiazdong.Calculatorutils;
    
    import java.util.Stack;
    
    
    
    /**
     * 计算器工具类
     * 完成整数、浮点的加、减、乘、除、括号运算
     * 
     * 禁忌:如果出现.5表示0.5,则结果不正确
     * @author xiazdong
     *
     */
    public class CalculatorUtils {
    	/**
    	 * 将中缀表达式转换成后缀表达式 规则: 1.如果是操作数,则添加到输出流 2.如果是(,则添加栈中;
    	 * 3.如果是),则将栈中操作符移入输出流,直到(为止,()不添加入输出流 4.如果是一般操作符(+-*
    	 * /),则加入栈之前,需要检查栈中的操作符的优先级,如果栈顶优先级比添加的优先级高,则将栈顶操作符移入输出流,否则直接添加操作符;
    	 */
    	
    	public static String calculate(String str){
    		return calculateReversePolish(exchangeToReversePolish(str));
    	}
    	
    	private static String exchangeToReversePolish(String str) {
    		// 1.创建Stack
    		Stack<String> s = new Stack<String>();
    		// 2.创建输出流字符串
    		StringBuilder builder = new StringBuilder();
    		// 3.解析中缀表达式
    		// 3.1 如果是读到数字,则接着读,直到读到操作符为止
    		for (int i = 0, numLenCount = 1; i < str.length(); i += numLenCount) {
    			char ch = str.charAt(i);
    			String operand = ch + "";
    			numLenCount = 1;
    			if ((ch + "").matches("\\d{1}")) {
    				numLenCount = 1;
    				char nextChar = 0;
    				if ((i + numLenCount) < str.length()) { // 下一个字符是否超过边界长度
    					nextChar = str.charAt(i + numLenCount);
    					while ((nextChar + "").matches("[.\\d{1}]")) {
    						operand += nextChar;
    						if ((i + numLenCount + 1) < str.length()) {
    							nextChar = str.charAt(i + numLenCount + 1);
    							numLenCount++;
    						} else {
    							numLenCount++;
    							break;
    						}
    					}
    				}
    				operand += " ";
    				builder.append(operand);
    
    			} else {
    				if (ch == '(') {
    					s.push(ch + "");
    				} else if (ch == '+' || ch == '-') {
    					while (s.size() > 0 && s.peek().matches("[-+*/]")) {
    						builder.append(s.pop() + " ");
    					}
    					s.push(ch + "");
    				} else if (ch == '*' || ch == '/') {
    					while (s.size() > 0 && s.peek().matches("[*/]")) {
    						builder.append(s.pop() + " ");
    					}
    					s.push(ch + "");
    				} else if (ch == ')') {
    					while (s.size() > 0 && !s.peek().equals("(")) {
    						builder.append(s.pop() + " ");
    					}
    					s.pop();
    				}
    			}
    		}
    		while (s.size() > 0) {
    			builder.append(s.pop() + " ");
    		}
    		System.out.println(builder);
    		return builder.toString();
    
    	}
    
    	/**
    	 * 计算后缀表达式
    	 * 
    	 */
    	private static String calculateReversePolish(String str) {
    
    		String[] splitStr = str.split(" ");
    		Stack<String> s = new Stack<String>();
    		for (int i = 0; i < splitStr.length; i++) {
    			String ch = splitStr[i];
    			if (ch.matches("\\d+.\\d+")||ch.matches("\\d+")) {
    				s.push(ch);
    			} else {
    				if (s.size() >= 2) {
    					String c1 = s.pop();
    					String c2 = s.pop();
    					if (ch.equals("+")) {
    						if(c1.contains(".")||c2.contains(".")){
    							s.push(String.valueOf((Double.parseDouble(c2 + "") + Double
    								.parseDouble(c1 + ""))));
    						}
    						else{
    							s.push(String.valueOf((Integer.parseInt(c2 + "") + Integer
    									.parseInt(c1 + ""))));
    						}
    						
    					} else if ("-".equals(ch)) {
    						if(c1.contains(".")||c2.contains(".")){
    						s.push(String.valueOf((Double.parseDouble(c2 + "") - Double
    								.parseDouble(c1 + ""))));
    						}
    						else{
    							s.push(String.valueOf((Integer.parseInt(c2 + "") - Integer
    									.parseInt(c1 + ""))));
    						}
    					} else if ("*".equals(ch)) {
    						if(c1.contains(".")||c2.contains(".")){
    						s.push(String.valueOf((Double.parseDouble(c2 + "") * Double
    								.parseDouble(c1 + ""))));
    						}
    						else{
    							s.push(String.valueOf((Integer.parseInt(c2 + "") * Integer
    									.parseInt(c1 + ""))));
    						}
    					} else if ("/".equals(ch)) {
    						s.push(String.valueOf((Double.parseDouble(c2 + "") / Double
    								.parseDouble(c1 + ""))));
    					}
    
    				} else {
    					System.out.println("式子有问题!");
    					return null;
    				}
    			}
    		}
    		return s.pop();
    	}
    }
    


    展开全文
  • 有趣的数据结构算法10——利用栈计算后缀表达式的结果解题思路实现代码GITHUB下载连接 在前一天已经利用栈完成2进制到8进制的转换。但是栈的应用方面还有很多,本次我将讲解如何计算后缀表达式的结果。 解题思路 ...

    有趣的数据结构算法10——后缀表达式(PRN)介绍及利用栈计算后缀表达式的结果

    在前一天已经利用栈完成2进制到8进制的转换。但是栈的应用方面还有很多,本次我将讲解如何计算后缀表达式的结果。
    在这里插入图片描述

    解题思路

    后缀表达式(PRN)也叫逆波兰表达式,是在计算机中用于求值的一种方式,其求值过程可以用到栈来辅助存储。
    在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示,如1+2。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示,如12+。
    它的优势在于只用两种简单操作,入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下:
    如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。
    中缀表达式转换到后缀表达式公式
    假定待求值的后缀表达式为:1 2 + 5 3 6 + * + 7 - ,其实际上为1+2+5*(3+6)-7。其求值过程如下:
    1、遍历表达式,遇到1和2,压入栈中。此时栈如图所示:

    示例1
    2、接着读到+号,弹出2与1,执行加法运算,得到3,再次入栈。此时栈如图所示:

    示例2
    3、遇到5、3和6,压入栈中。此时栈如图所示:

    示例3
    4、接着读到+号,弹出6与3,执行加法运算,得到9,再次入栈。此时栈如图所示:

    示例4
    5、接着读到*号,弹出9与5,执行加法运算,得到45,再次入栈。此时栈如图所示:

    示例5
    6、接着读到+号,弹出45与3,执行加法运算,得到48,再次入栈。此时栈如图所示:

    示例6
    7、遇到7,压入栈中。此时栈如图所示:

    示例7
    8、接着读到-号,弹出7与48,执行加法运算,得到41,再次入栈。
    9、由于表达式已结束,读出栈内的最后一个元素,就是结果41。

    实现代码

    #include <stdio.h>
    #include <stdlib.h>
    #define Maxsize 10
    typedef double Ele;
    
    struct stack
    {
    	Ele* top;
    	Ele* bottom;
    	int stacksize;
    };
    
    typedef struct stack* Stack;
    
    void init(Stack s){			//初始化栈
    	Ele *p;
    	p = (Ele*)malloc(Maxsize * sizeof(Ele));
    	if (p == NULL){
    		printf("error");
    		exit(1);
    	}
    	s->top = s->bottom = p;
    	s->stacksize = Maxsize;
    }
    
    void PUSH(Stack s, Ele data){		//入栈
    	int length;
    	length = s->top - s->bottom;
    	if (length >= s->stacksize){
    		s->bottom = (Ele*)realloc(s->bottom,(s->stacksize + Maxsize) * sizeof(Ele));
    		if (s->bottom == NULL){
    			printf("内存分配失败\n");
    			exit(1);
    		}
    		s->stacksize = s->stacksize + Maxsize;//更新stacksize的值
    		s->top = s->bottom + length; //更新top的值
    	}
    	*(s->top) = data;
    	s->top++;
    }
    Ele POP(Stack s){					//出栈
    	Ele num;
    	if (s->top == s->bottom){
    		printf("栈内没有元素了!\n");
    		exit(1);
    	}
    	s->top--;
    	num = *(s->top);
    	return num;
    }
    
    int main(){
    	struct stack s;			//定义栈
    	char c = 0,str[10];		//c用于从键盘获取字符,str用于存储每一轮输入的数字,之后会转化成double类型
    	Ele a1, a2, num;		//a1,a2用于栈的运算
    	int i = 0;				//temp量
    
    
    	init(&s);				//初始化栈
    	printf("请输入一个算式:");		
    
    	scanf("%c", &c);		//输入一个字符
    	while (c != '#')
    	{
    		while ((c <= '9' && c >= '0') || c == '.'){	//该部分用于获取一个double类型的数字
    			str[i++] = c;
    			str[i] = '\0';
    			if (i >= 10){
    				printf("输入数据过大");
    				exit(1);
    			}
    			scanf("%c", &c);
    			if (!(c <= '9' && c >= '0') && !(c == '.')){
    				a1 = atof(str);						//该函数用于将字符串转化位double
    				PUSH(&s, a1);
    				i = 0;
    				break;
    			}
    		}
    		switch (c)								//判断是否属于加减乘除
    		{
    		case '+': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 + a1);
    			break;
    		case '-': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 - a1);
    			break;
    		case '*': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 * a1);
    			break;
    		case '/': 
    			a1 = POP(&s);
    			a2 = POP(&s); 
    			PUSH(&s, a2 / a1);
    			break;
    		case ' ':
    			break;
    		case '#':
    			break;
    		default:
    			printf("输入符号错误!\n");
    			break;
    		}
    		scanf("%c", &c);
    	}
    	num = POP(&s);
    	printf("%.3f\n", num);
    
    	return 0;
    }
    

    GITHUB下载连接

    https://github.com/bubbliiiing/Data-Structure-and-Algorithm

    希望得到朋友们的喜欢。
    有问题的朋友可以提问噢。

    展开全文
  • 原理不赘述,随便找个博客看看后缀表达式即其计算 原理简单,实现起来有几个小问题: Q1:A+B*C的后缀变表达式为ABC*+,当ABC为具体的1、2、3时,后缀表达式为123*+, 123怎么理解,1和2和3还是12和3还是1和23... ...

    原理不赘述,随便找个博客看看后缀表达式即其计算

    原理简单,实现起来有几个小问题:

    Q1:A+B*C的后缀变表达式为ABC*+,当ABC为具体的1、2、3时,后缀表达式为123*+, 123怎么理解,1和2和3还是12和3还是1和23...

    A1:用||间隔数字,如|1||2||3|*+就很明确了。

    Q2:输入是字符串,计算要int/double

    A2:所以需要自己写一个一个字符串转换为int/double的函数,目前写的字符串转换成int,毕竟double不精确,如果想用double,可以自己实现一个分数类,重载各种运算符即可,要精确结果,用分数表示,要小数结果,分子除以分母

    Q3:如何拓展其他云算法

    A3:实现一个add_operation即可,并提供计算方法,优先级信息

    C++ class封装实现

    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    
    //简单的函数直接写成内联的了
    class caculator
    {
    public:
        caculator()
        {
            initial_priority();
        }
        ~caculator()
        {
            
        }
        int add_operation(char op, int priority, int(*func)(const int, const int))
        {
            int status = 0;
            if (this->priority[op] == 0)
            {
                this->priority[op] = priority;
                this->op_func[op] = func;
                status = 1;
            }
            return status;
        }
        
        int get_result(string s);
        
    private:
        int priority[128];
        int (*op_func[128])(const int, const int);
        static int get_num(string formula, int &index);
        void initial_priority();
        string get_postfix(string formula);
    };
    
    //主要的功能函数
    //初始化运算符优先级信息
    void caculator::initial_priority()
    {
        op_func['+'] = op1;
        op_func['-'] = op2;
        op_func['*'] = op3;
        op_func['/'] = op4;
        
        priority['+'] = 2;
        priority['-'] = 2;
        priority['*'] = 3;
        priority['/'] = 4;
        priority['('] = 1;
    }
    //string->int
    int caculator::get_num(string formula, int &index)
    {
        int sum = 0;
        while (formula[index] >= '0' && formula[index] <= '9')
        {
            sum = sum * 10 + formula[index] - '0';
            index++;
        }
        return sum;
    }
    //中缀表达式变后缀表达式
    string caculator::get_postfix(string formula)
    {
        string post = "";
        vector<int> num;
        vector<char> op;
    
        for (int i = 0; i < formula.length(); i++)
        {
            char c = formula[i];
            if (c == ' ') continue;
            if (isdigit(c))
            {
                
                int var = get_num(formula, i);
                post += (string("|") + to_string(var) + string("|"));
            }
            c = formula[i];
            if (!isdigit(c))
            {
                if (c == '(')
                {
                    op.push_back(c);
                }
                else if (c == ')')
                {
                    while (op.back() != '(')
                    {
                        post += op.back();
                        op.pop_back();
                    }
                    op.pop_back();
                }
                else
                {
                    while (op.size() > 0 && priority[op.back()] >= priority[c])
                    {
                        post += op.back();
                        op.pop_back();
                    }
                    op.push_back(c);
                }
            }
        }
        
        while (op.size() != 0)
        {
            post += op.back();
            op.pop_back();
        }
        
        return post;
    }
    //计算
    int caculator::get_result(string s)
    {
        vector<int> num;
        string postfix = get_postfix(s);
        int x, y;
        
        for (int i = 0; i < postfix.length(); i++)
        {
            char c = postfix[i];
            if (c == '\0') continue;
            if (c != '|' && isdigit(c))
            {
                x = get_num(postfix, i);
                num.push_back(x);
            }
            c = postfix[i];
            if (c != '|' && !isdigit(c))
            {
                x = num.back();
                num.pop_back();
                y = num.back();
                num.pop_back();
                num.push_back(op_func[c](y, x));
            }
        }
        return num[0];
    }
    
    //main
    int main()
    {
        caculator c;
        
        cout << c.get_result("1+2*(3+4/2)") << endl;
        
        return 0;
    }
    

    随便写写,可能有bug,并没有仔细debug

    展开全文
  • 0.1) 本文旨在总结 中缀表达式转后缀表达式并计算后缀表达式的值 的步骤,并给出源代码实现; 0.2) 本文中涉及到的源代码均为原创,是对中缀转后缀和计算后缀的简单实现,(旨在理清它的原理),故源代码中 考虑的...
  • 计算后缀表达式的值

    2019-09-25 09:14:52
    题目描述 ...计算机计算后缀表达式的过程为,从左到右,遍历表达式,如果当前位是数字,那么先将其暂存,继续往后遍历;如果碰到运算符,那么就取出最近暂存的两个数字,并计算出值,然后将该值继续...
  • 因为数据结构老师布置了栈的后缀表达式实验,经过思考,有以下反思。 中缀表达式转换为后缀表达式 关于括号,直接将括号里面的符号加入后缀表达式。 关于数字,直接推入后缀表达式 遇到±符号,如果栈为空或者栈顶...
  • 计算后缀表达式的过程中,你可以根据需要调用以上操作。因为表达式的计算结果可能是浮点数,所以这里将栈的数据元素类型设置为了double类型。 typedef double T; // 数据元素类型 此外,为了计算后缀表达式,我们...
  • 后缀表达式:就是将运算符挪到操作数后面,但这样的挪动是有规则的,例如上式转换后缀表达式后是这样的:"9 3 1-4*+10 2/+" 中缀转后缀表达式规则: 从左到右遍历中缀表达式中的每一个·数字和符号: 1.如果是...
  • 什么叫后缀表达式 使用栈的数据结构来计算后缀表达式 代码
  • 计算后缀表达式的算法
  • 问题 E: 计算后缀表达式 时间限制: 1 Sec 内存限制: 128 MB 题目描述 后缀表达式是将运算符置于两个运算对象之后的一种表达方法,例如 “3+4” 用写成后缀表达式后就是 “3 4 +”,而 “3-4*5” 写成...
  • 这篇博客我们来介绍如何计算后缀表达式,并使用Java实现。 计算后缀表达式的流程: 从左至右扫描表达式,遇到数字时,将数字压入堆栈。 遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 ...
  • 目标:中缀表达式转换为后缀表达式 规则: 从左到右遍历中缀表达式,遇到字符按如下方式处理; 1) 操作数 输出 2) 操作符(+,-,*,/) 判断优先级。优先级高(大于栈顶操作符),则它进栈; 优先级低(低于栈顶...
  • 逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍,下面是一些例子:    正常的表达式 逆波兰表达式    a+b ---> a,b,+    a+(b-c) ---> a,b,c,-,+    a+(b-c)d --...
  • 2909: 计算后缀表达式的值 题目描述 所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。 ...
  • 计算后缀表达式的过程是一个很好玩的过程,而且很简单哦!这里呢,有个计算的技巧,就是:遇到数字直接入栈,遇到运算符就计算!  后缀表达式也叫逆波兰表达式,求值过程可以用到栈来辅助存储;  假定待求值的...
  • 【数据结构】计算后缀表达式的值

    千次阅读 2019-01-20 17:33:46
    我们平常使用的计算表达式都是中缀表达式,而输入计算机后会转换为后缀表达式,即计算机只能计算后缀表达式,那么如何将一个中缀表达式转换为一个后缀表达式? 算法 1)从左到右扫描后缀表达式字符串 2)初始化一...
  • 将中缀表达式转为后缀表达式后,利用栈来计算后缀表达式的结果
  • 使用堆栈计算后缀表达式

    千次阅读 2019-01-29 16:01:18
    使用堆栈计算后缀表达式 一、实现栈结构 根据栈的先进后出的特点,很容易设置栈结构的接口:入栈、出栈、判空、size()等。可以用线性表的方法来实现一个栈结构,其实也就两种,用链表或数组实现栈。 但是,在C++...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,132
精华内容 1,652
关键字:

计算后缀表达式