精华内容
下载资源
问答
  • C++中缀表达式求值

    2010-12-05 08:39:03
    使用栈将中缀表达式转化为后缀表达式然后求值 语言C++
  • 给你一个中缀表达式,就是平常的算术式,比如这样的1+4/2*3+4 计算结果 没有提交,我编几个样例把。 【输入样例】: (((1))) (((1+1))) 1+4/2*3+4 1+4/(2*3)+4 1+120/(20*3)+1 【输出样例】: 1 2 11 5 4 ...

    problem

    • 给你一个中缀表达式,就是平常的算术式,比如这样的1+4/2*3+4
    • 求计算结果

    没有提交,我编几个样例把。
    【输入样例】:

    (((1)))
    (((1+1)))
    1+4/2*3+4
    1+4/(2*3)+4
    1+120/(20*3)+1
    

    【输出样例】:

    1
    2
    11
    5
    4
    

    【中缀表达式结果】

    1.
    1.1.+
    1.4.2./3.*+4.+
    1.4.2.3.*/+4.+
    1.120.20.3.*/+1.+
    

    solution

    【中缀表达式转后缀:】

    1)如果遇到操作数,我们就直接将其输出。
    2)如果遇到操作符(包括左括号),则我们将其放入到栈中。
    3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。
    4)如果遇到任何其他的操作符,如(“+”, “*”,“(”)等,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到" ) "的情况下我们才弹出" ( ",其他情况我们都不会弹出" ( "。
    5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。
    ps)对于两位的数字,在转为中缀的时候记得加个点,方便求值
    

    【后缀表达式求值:】

    1)遇到数字时,将数字压入堆栈
    2)遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次栈顶元素 op 栈顶元素),并将结果入栈。
    
    #include<bits/stdc++.h>
    using namespace std;
    int Youxianji(char op){
    	if(op=='*'||op=='/')return 2;
    	if(op=='+'||op=='-')return 1;
    	if(op=='(')return 0;
    }
    void ToHouzhui(string str, string& ans){
    	stack<char>stk;
    	ans = "";
    	int i =0;
    	while(i<str.size()){
    		if(str[i]>='0' && str[i]<='9'){
    			//ans += str[i];
    			int t = 0;
    			while(str[i]>='0' && str[i]<='9'){
    				t = t*10+str[i]-'0';
    				i++;
    			}
    			ans += to_string(t)+".";
    		}else{
    			if(stk.empty()){
    				stk.push(str[i]);
    			}else if(str[i]=='('){
    				stk.push(str[i]);
    			}else if(str[i]==')'){
    				while(stk.top()!='('){
    					ans += stk.top();
    					stk.pop();
    				}
    				stk.pop();
    			}else{
    				while(Youxianji(stk.top())>=Youxianji(str[i])){
    					ans += stk.top();
    					stk.pop();
    					if(stk.empty())break;
    				}
    				stk.push(str[i]);
    			}
    			i++;
    		}
    	}
    	while(stk.size()){
    		ans += stk.top();
    		stk.pop();
    	}
    }
    int culate(string str){
    	stack<int>stk;
    	int ans = 0, i = 0;
    	while(i < str.size()){
    		if(str[i]>='0'&&str[i]<='9'){
    			//stk.push(str[i]-'0');
    			int t = 0;
    			while(str[i]!='.'){
    				t = t*10+str[i]-'0';
    				i++;
    				//cout<<t<<endl;
    			}
    			i++;
    			//cout<<t<<endl;
    			stk.push(t);
    		}else{
    			int a = stk.top();  stk.pop();
    			int b = stk.top();  stk.pop();
    			int tmp;
    			if(str[i]=='+')tmp = b+a;
    			if(str[i]=='-')tmp = b-a;
    			if(str[i]=='*')tmp = b*a;
    			if(str[i]=='/')tmp = b/a;
    			stk.push(tmp);
    			i++;
    		}
    	}
    	return stk.top();
    }
    
    int main(){
    	string s,t;
    	while(cin>>s){
    		ToHouzhui(s,t);
    		//cout<<t<<endl;
    		cout<<culate(t)<<endl;
    	}
    	return 0;
    }
    
    
    展开全文
  • 中缀表达式转后缀表达式 代码 #include <iostream> using namespace std; const int N = 100010; char stk[N]; int top; int pr[200]; // 优先级 // 中缀转后缀 string func(string s) { pr['+'] = pr['-...

    中缀转后缀

    在这里插入图片描述

    代码

    #include <iostream>
    
    using namespace std;
    
    const int N = 100010;
    char stk[N];
    int top;
    int pr[200];    // 优先级
    
    // 中缀转后缀
    string func(string s)
    {
        pr['+'] = pr['-'] = 1;
        pr['*'] = pr['/'] = 2;
        pr['('] = pr[')'] = 3;
        string res;
        for (auto c : s)
        {
            if (c >= 40 && c <= 47)
            {
                if (!top || pr[c] > pr[stk[top]]) stk[++ top] = c;
                else
                {
                    while (pr[c] <= pr[stk[top]]) res += stk[top --];
                    stk[++ top] = c;
                }
            }
            else res += c;
        }
        res += stk[top --];
    
        return res;
    }
    
    int main()
    {
        string s;
        cin >> s;
        while (s != "-1")
        {
            cout << func(s) << endl;
            cin >> s;
        }
    
        return 0;
    }
    

    输出结果

    在这里插入图片描述

    中缀表达式求值

    代码

    #include <iostream>
    #include <stack>
    #include <unordered_map>
    
    using namespace std;
    
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    stack<char> op;
    stack<float> num;
    
    void eval()
    {
        float x;
        char c = op.top(); op.pop();
        float b = num.top(); num.pop();
        float a = num.top(); num.pop();
        if (c == '/') x = a / b;
        else if (c == '*') x = a * b;
        else if (c == '+') x = a + b;
        else x = a - b;
        num.push(x);
    }
    
    float func(string s)
    {
        for (int i = 0 ; i < s.size() ; i ++)
        {
            char c = s[i];
            if (isdigit(c))
            {
                int j = i;
                if (j + 1 < s.size() && isdigit(s[j + 1])) j ++;
                float val = stof(s.substr(i, j - i + 1));
                num.push(val);
                i = j;
            }
            else if (c == '(') op.push(c);
            else if (c == ')')
            {
                while (op.top()!= '(') eval();
                op.pop();   // 过滤掉 '('
            }
            else
            {
                while (!op.empty() && pr[c] <= pr[op.top()]) eval();
                op.push(c);
            }
        }
        while (!op.empty()) eval();
        return num.top();
    }
    
    int main()
    {
        string s;
        cin >> s;
        while (s != "-1")
        {
            cout << func(s) << endl;
            cin >> s;
        }
        return 0;
    }
    

    输出结果

    在这里插入图片描述

    展开全文
  • 这个算法比较难想,是把表达式expression看成用+号或-分开 term看成用*号或/号分开 factor看成括号或一个数,形成递归 #include&lt;iostream&gt; #include&lt;cstring&gt; #include&lt;...

    这个算法比较难想,是把表达式expression看成用+号或-分开

    term看成用*号或/号分开

    factor看成括号或一个数,形成递归

    #include<iostream>  
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    int factor_value();     // 求一个因子的值
    int term_value();       // 求一个项的值
    int expression_value(); // 求一个表达式的值
    
    int main()
    {
    	cout << expression_value() << endl;
    	return 0;
    }
    
    int expression_value()  //求一个表达式的值
    {
    	int result = term_value(); // 求第一项的值
    	bool more = true;
    	while (more)
    	{
    		char op = cin.peek();  // 看一个字符,不取走
    		if (op == '+' || op == '-')
    		{
    			cin.get();          // 从输入流取走字符
    			int value = term_value();
    			if (op == '+')
    				result += value;
    			else
    				result -= value;
    		}
    		else
    			more = false;
    	}
    	return result;
    }
    
    int term_value()  // 求一个项的值
    {
    	int result = factor_value(); // 求一个因子的值
    	while (true)
    	{
    		char op = cin.peek();
    		if (op == '*' || op == '/')
    		{
    			cin.get();          // 从输入流取走字符
    			int value = factor_value();
    			if (op == '*')
    				result *= value;
    			else
    				result /= value;
    		}
    		else
    			break;
    	}
    	return result;
    }
    
    int factor_value()   // 求一个因子的值
    {
    	int result = 0;
    	char c = cin.peek();
    	if (c == '(')
    	{
    		cin.get();    // 去左括号
    		result = expression_value();  // 求表达式的值
    		cin.get();    // 去右括号
    	}
    	else
    	{
    		// 如果读到是一个整数,注意这里不是只有一位
    		while (isdigit(c))
    		{
    			result = 10 * result + c - '0';
    			cin.get();
    			c = cin.peek();
    		}
    	}
    	return result;
    }

     

    展开全文
  • C++中缀表达式求值(布尔表达式)

    千次阅读 2018-04-14 18:28:15
    void qiuzhi() { //后缀表达式求值 bool r = 1; char x, y; while (q.size()) { // 如果遇到运算数,运算数入栈,队列出队 if (q.front() == 'V' || q.front() == 'F') { s.push(q.front()); q.pop()...

    总时间限制: 

    1000ms

    内存限制: 

    65536kB

    描述

    The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next: 

    Expression: ( V | V ) & F & ( F | V )


    where V is for True, and F is for False. The expressions may include the following operators: ! for not , & for and, | for or , the use of parenthesis for operations grouping is also allowed. 

    To perform the evaluation of an expression, it will be considered the priority of the operators, the not having the highest, and the or the lowest. The program must yield V or F , as the result for each expression in the input file. 

    输入

    The expressions are of a variable length, although will never exceed 100 symbols. Symbols may be separated by any number of spaces or no spaces at all, therefore, the total length of an expression, as a number of characters, is unknown. 

    The number of expressions in the input file is variable and will never be greater than 20. Each expression is presented in a new line, as shown below. 

    输出

    For each test expression, print "Expression " followed by its sequence number, ": ", and the resulting value of the corresponding test expression. Separate the output for consecutive test expressions with a new line. 

    Use the same format as that shown in the sample output shown below. 

    样例输入

    ( V | V ) & F & ( F| V)
    !V | V & V & !F & (F | V ) & (!F | F | !V & V)
    (F&F|V|!V&!F&!(F|F&V))

    样例输出

    Expression 1: F
    Expression 2: V
    

    Expression 3: V

     

    #include<iostream>  
    #include<cstdio>  
    #include<stack>  
    #include<queue>  
    #include<string>  
    using namespace std;
    
    stack<char> s;
    queue<char> q;  //存后缀表达式   
    string c;
    
    int f(char c) {  //求表达式的优先级  
    	if (c == '(') return 4;
    	if (c == '!') return 3;
    	if (c == '&') return 2;
    	if (c == '|') return 1;
    }
    
    int f2(char c) {  //转换F和V  ,将逻辑表达式转换为数字 
    	if (c == 'F') return 0;
    	else return 1;
    }
    
    void houzui() {   //求表达式对应的后缀表达式   
    				  //初始化栈 
    	while (s.size()) {
    		s.pop();
    	}
    	//字符串中去手动去空格 
    	for (int i = 0; i<c.size(); i++) {
    		if (c[i] != ' ') {  //除去空格   
    							//如果遇到逻辑表达式,直接加入到队列中,用队列来放后缀表达式 
    			if (c[i] == 'F' || c[i] == 'V') q.push(c[i]);
    			else if (c[i] == '!'&&s.size() && s.top() == '!') { //遇到连续两个!!抵消,直接将!出栈 
    				s.pop();
    			}
    			else if (!s.size()) s.push(c[i]);  //如果栈为空,遇到逻辑符号直接入栈 
    			else if (c[i] == ')') {           //如果是右括号,则弹出对应左括号前的所有的运算符 ,加入到队列中 
    				while (s.top() != '(') {
    					q.push(s.top());
    					s.pop();
    				}
    				s.pop();
    				continue;
    			}
    			else if (f(s.top()) == 4 || (f(c[i])>f(s.top()))) s.push(c[i]);  //左括号优先级最高,入栈后优先级最低, 
    			else if (f(s.top()) != 4 && f(c[i]) <= f(s.top())) {
    				q.push(s.top());
    				s.pop();              //如果遇到运算符没有栈顶运算符级别高,栈顶运算符加入到队列,一直循环 
    				while (s.size() && f(s.top()) != 4 && f(c[i]) <= f(s.top())) {      //弹出不低于c[i]优先级的运算   
    					q.push(s.top());
    					s.pop();
    				}
    				s.push(c[i]);  //将当前运算符加入到队列 
    			}
    		}
    	}
    	//最后将所有运算符加入到栈中 
    	while (s.size()) {
    		q.push(s.top());
    		s.pop();
    	}
    }
    
    void qiuzhi() {     //后缀表达式求值   
    	bool r = 1;
    	char x, y;
    	while (q.size()) {
    		// 如果遇到运算数,运算数入栈,队列出队 
    		if (q.front() == 'V' || q.front() == 'F') {
    			s.push(q.front());
    			q.pop();
    		}
    		// 遇到运算符,弹出栈顶两个元素,进行逻辑运算,结果入栈 
    		else {
    			// 逻辑与运算 
    			if (q.front() == '&') {
    				x = s.top();
    				s.pop();
    				y = s.top();
    				s.pop();
    				r = f2(x) && f2(y);
    				if (r == 1)
    					s.push('V');
    				else
    					s.push('F');
    			}
    			else if (q.front() == '|') {
    				// 逻辑或运算 
    				x = s.top();
    				s.pop();
    				y = s.top();
    				s.pop();
    				r = f2(x) || f2(y);
    				if (r == 1)
    					s.push('V');
    				else
    					s.push('F');
    			}
    			else {
    				// 逻辑非运算,只弹一个数 
    				x = s.top();
    				s.pop();
    				if (f2(x) == 1)
    					s.push('F');
    				else
    					s.push('V');
    			}
    			q.pop();
    		}
    	}
    }
    
    int main()
    {
    	int i = 0;
    	while (getline(cin, c))
    	{
    		i++;
    		houzui();
    		qiuzhi();
    		printf("Expression %d: %c\n", i, s.top());
    	}
    	
    
    	
    }

     

     

    展开全文
  • 这里写自定义目录标题中缀表达式求值代码C++中缀转后缀算法流程图后缀转二叉树流程图需要注意的点代码 中缀表达式求值代码C++ 中缀表达式求值比较合理的做法是: 中缀转后缀 后缀转二叉树 二叉树求值 中缀转后缀 ...
  • C++实现计算一个字符串形式的中缀表达式。代码实现了算术表达式的词法分析,能支持多位整型的计算。思路是将中缀表达式转化成后缀表达式计算。
  • 采用栈和队列数据结构及C++程序设计语言实现中缀表达式求值#数据结构实验#栈和队列应用#C++程序设计语言
  • 中缀表达式求值

    2016-10-25 22:38:54
    c++ 中缀表达式转后缀表达式再求值 dev编译通过
  • C++中缀表达式求值

    千次阅读 2019-07-24 21:05:14
    文章目录前言 & 剧情思考实现方法参考代码后话 前言 & 剧情 任务背景: 话说,从前计算机界有三大帮派,一个叫做后缀表达式,有一个叫做波兰的帝国撑腰,也叫作波兰...中缀表达式在计算机界身位卑微,...
  • 一、使用说明1.1 项目简介表达式求值是程序设计语言编译中的一个最基本的问题,就是将一个表达式转化为逆波兰表达式并求值。具体要求是以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,并利用给定的...
  • 中缀表达式求值 C++

    千次阅读 2016-08-22 10:58:09
    中缀表达式求值 C++实现四则运算
  • C++实现中缀表达式求值代码

    千次阅读 2014-04-17 20:08:24
    给出中缀表达式字符串,
  • 中缀表达式求值 Python C++

    千次阅读 2018-10-02 01:42:43
    实现对中缀表达式直接求值,新算法还是从左到右扫描中缀表达式, 但同时使用两个栈,一个暂存操作符,一个暂存操作数,来进行求值。 (支持 + - * / ^ 五种运算)   输入格式: 共1行,为1个字符串,即一个中缀...
  • [C++]中缀表达式求值

    千次阅读 2019-01-09 19:32:33
    Step2: 后缀表达式求值 算法部分 Step1: 先声明两个需要用到的容器:stack,string # include # include . . . stack < char > s ; //push the operators in it string ans ; //save the ...
  • } //后缀表达式计算 void calculate(string s){ stack ops; stack vals; int left, right; for(int i = 0; i (); i++){ if(s[i] >= '0' && s[i] ){ //数字,入数字栈 string s2 = ""; while(s[i] >= '0' && s[i] ){...
  • 简易数据结构
  • C++数据结构 栈实现中缀表达式计算 ...取出optr的栈顶optrTop,当optrTop和ch同时=“=”,整个表达式求值完毕,opnd栈顶元素为表达式值 若ch不是操作符,将字符放回输入流,读操作数operand,加入opn

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 230
精华内容 92
关键字:

c++中缀表达式求值

c++ 订阅