算数表达式

我们通常把运算符号放在运算数的中间，再用括号表示优先级别，比如a+b*c 和(a+b)*c，但在计算机为了正确存储算数表达式，还需要存储括号，非常麻烦，所以人们发明了前缀和后缀表达方法。

算数表达式可以分为前缀(prefix)、后缀(postfix)、中缀(infix)。
中缀表达式是我们通常用的形式，就是把运算符号放到两个运算数中间，但需要用括号来标定优先级，这在计算机处理上比较麻烦，所以在计算机中用前缀或后缀表达式来处理。

Infix Notation	Prefix Notation	Postfix Notation
a + b	+ a b	a b +
(a + b) * c	* + a b c	a b + c *
a * (b + c)	* a + b c	a b c + *
a / b + c / d	+ / a b / c d	a b / c d / +
(a + b) * (c + d)	* + a b + c d	a b + c d + *
((a + b) * c) – d	– * + a b c d	a b + c * d –

洛谷：p1981

#include <iostream>
#include <stack>
using namespace std;
stack <int> x;//一个存数字并在最后把它们相加的栈
int main()
{
	int a,b;
	char c;
	cin>>a;//先输入一个数，以后符号+数字输入
	int m=10000;
	a=a%m;//必须的操作
	x.push(a);//压入栈中
	while(cin>>c>>b){
		if(c=='*'){//将*之前的数字与*之后的数字积存入
		
			a=x.top();
			x.pop();
			x.push(a*b%m);
		}
		else//将b存入
			x.push(b);
	}
	a=0;
	while(x.size()){
		a+=x.top();
		x.pop();
	}
    	a%=m;//取模
	cout<<a<<endl;
	return 0;
}

acwing3302
计算式:(12+2)*(13-2*3)

/**************************************************************** 
 * Description: 输出算术式结果 例如：(12+2)/(13-2*3)
 * Author: Alex Li
 * Date: 2023-09-30 16:06:10
 * LastEditTime: 2023-10-10 14:15:26
****************************************************************/
#include <iostream>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
stack <int> num;
stack <char>  op;

//计算
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 if(c=='/')x=a/b;
    num.push(x);//把式子计算好，重新放回去 
}
int main(){
    string str;
    cin>>str;
    //设定符号优先级，采用map数据结构，也可以采用结构体或数组。
    map<char, int> pr;
    pr.insert(pair<char, int>('+',1));
    pr.insert(pair<char, int>('-',1));
    pr.insert(pair<char, int>('*',2));
    pr.insert(pair<char, int>('/',2));
   
    for (int i = 0; i <str.size(); i++){
        char c=str[i];
        if(isdigit(c)){//isdigit函数主要用于检查其参数是否为十进制数字字符。
            int x=0,j=i;
            while(j<str.size()&&isdigit(str[j])){
                x=x*10+str[j++]-'0';
            }
            i=j-1;
            num.push(x);
        }
        else if(c=='(')op.push(c);
        else if(c==')'){ 
            while(op.top()!='(')eval();
            op.pop();
        }
        else{
            while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[c])eval();
            //判断，如果符号栈里有符号，并且不是'('，而且新读的操作符优先级小于等于符号栈顶符号的有级，则计算。
            op.push(c); //把新读到的符号压倒栈里。
        }
     
    }
      while(op.size())eval();
      cout<<num.top()<<endl;
      return 0;

}

Quizzes

小测验-算数表达式

Previous Quiz

Back to Lesson

Next Quiz

数据结构与算法

算数表达式