3 条题解

  • 0
    @ 2025-11-27 14:50:28 
    #include <bits/stdc++.h>
using namespace std;

const int M = 10000;

int main(){
    stack<long long> stk;
    long long num;
    char op;
    
    cin >> num;
    stk.push(num % M); // 第一步取模
    
    while(cin >> op >> num){
        if(op == '*'){
            // 乘法优先级高，立刻取出栈顶计算，再放回去
            long long a = stk.top();
            stk.pop();
            long long b = num % M;
            stk.push((a * b) % M);
        } else if (op == '+'){
            // 加法优先级低，先入栈暂存，最后再加
            stk.push(num % M);
        }
    }
    
    // 【修正部分】循环结束后，栈里存的都是加数，需要求和
    long long ans = 0;
    while(!stk.empty()){
        ans = (ans + stk.top()) % M; // 累加并取模
        stk.pop();
    }
    
    cout << ans << endl;
    return 0;
}
    • 0
      @ 2025-11-27 14:50:10

      p1981 这道题（NOIP 2013 普及组 T2）是表达式求值中最基础的一类，因为它没有括号，只有加法和乘法。

      这道题的核心考点只有两个：运算优先级 和 取模运算。

      下面是解题的几个关键提示：

      1. 核心矛盾：先乘后加

      数学规则告诉我们，乘法优先级高于加法。 比如 1 + 2 * 3：

      • 如果你读到 1 + 2 就直接算出 3，然后再 * 3，结果是 9，这就错了。
      • 正确做法是：看到 + 时，先把 1 暂时存起来，等到 2 * 3 算完了，再把它们加起来。

      2. 数据结构神器：栈 (Stack)

      为了解决“先把数存起来，最后再加”的问题，栈是最合适的数据结构。

      算法逻辑： 我们可以把这个表达式看作是一堆数字的和。 比如 A + B * C + D * E * F，其实就是 A，(B*C)，(D*E*F) 这三项的和。

      • 遇到加号 +：说明前面的项已经结束了，把新读进来的数字压入栈中，等着最后求和。
      • 遇到乘号 *：说明还没完！
        • 把栈顶的数字取出来。
        • 和新读进来的数字相乘。
        • 把乘完的结果重新放回栈顶。
        • （因为乘法要优先算，算完了才能变成待加项）。

      3. 输入处理的技巧

      很多同学不知道怎么读取 数字 符号 数字 符号... 这种格式。 C++ 的 cin 有个特性，它会自动根据类型读取。

      推荐写法框架：

      long long num;
char op; // 运算符

cin >> num; // 先读第一个数
stack.push(num % 10000); // 进栈

// 利用 while 循环不断读取 "符号" 和 "下一个数字"
while (cin >> op >> num) {
    if (op == '*') {
        // 取栈顶，相乘，更新栈顶
        // 记得取模！
    } else if (op == '+') {
        // 直接进栈
        // 记得取模！
    }
}

      4. 坑点：只输出后 4 位

      题目要求“当答案长度多于 4 位时，请只输出最后 4 位”。 这其实就是暗示你：全程进行模 10000 运算。

      • 输入一个数，立刻 % 10000。
      • 乘法算完，立刻 % 10000。
      • 最后加法算完，立刻 % 10000。 这样既能满足题目输出要求，又能防止数据过大溢出（虽然这题数据不大，但养成好习惯很重要）。

      5. 最后的汇总

      当 while 循环结束（输入读取完毕）后，栈里面剩下的都是已经被算好的“加数”了（所有的乘法都在循环里被消化掉了）。 这时候，你只需要把栈里所有的数字弹出来累加，就是最终答案。

      加油！理清了“栈”的作用，这道题就迎刃而解了。

      这个版本答案错在哪里？

      #include <bits/stdc++.h>
using namespace std;

const int M=10000;

int main(){
    stack<long long> stk;
    long long num;
    char op;
    cin>>num;
    stk.push(num%M);
    while(cin>>op>>num){
        if(op=='*'){
            //出栈,相乘
            long long a=stk.top();
            stk.pop();
            long long b=num%M;
            stk.push((a*b)%M);
        }else if (op=='+'){
            //入栈
            stk.push(num%M);
        }
    }
    //最后栈里只剩一个数，就是答案
    cout<<stk.top()<<endl;
}

      你的代码在处理 乘法 的逻辑上是完全正确的，但是对于 加法 的逻辑有一个致命的误解，导致结果错误。

      致命错误：只存不加，最后只输出了“最后一项”

      请看这行代码：

      // 最后栈里只剩一个数，就是答案
cout << stk.top() << endl;

      这是错误的！ 栈里剩下的不只有一个数，而是所有等待相加的数。

      举个反例

      输入：1+1

      1. 读入 1，入栈。栈：[1]。
      2. 读入 +, 1。进入 else if (op=='+') 分支，入栈。栈：[1, 1]。
      3. 循环结束。
      4. 你的代码输出 stk.top()，也就是栈顶的 1。
      5. 实际答案应该是 2。

      你的逻辑漏洞

      你的代码策略是：

      • 遇到乘法 *：立刻算出来（正确，因为乘法优先级高）。
      • 遇到加法 +：把数压进栈里（正确，因为加法优先级低，要等后面的乘法算完了再说）。

      但是！ 当所有输入都结束后，栈里留下的全是那些“被加号隔开的数”。比如输入 1+2*3+4，循环结束后，栈里会有三个数：1、6（即2*3）、4。 你忘记了最后一步：把栈里剩下的所有数加起来！

      修改方案

      在 while 循环结束后，不要直接输出 top()，而是要写一个循环，把栈里的数一个个弹出来累加。

      修正后的代码

      #include <bits/stdc++.h>
using namespace std;

const int M = 10000;

int main(){
    stack<long long> stk;
    long long num;
    char op;
    
    cin >> num;
    stk.push(num % M); // 第一步取模
    
    while(cin >> op >> num){
        if(op == '*'){
            // 乘法优先级高，立刻取出栈顶计算，再放回去
            long long a = stk.top();
            stk.pop();
            long long b = num % M;
            stk.push((a * b) % M);
        } else if (op == '+'){
            // 加法优先级低，先入栈暂存，最后再加
            stk.push(num % M);
        }
    }
    
    // 【修正部分】循环结束后，栈里存的都是加数，需要求和
    long long ans = 0;
    while(!stk.empty()){
        ans = (ans + stk.top()) % M; // 累加并取模
        stk.pop();
    }
    
    cout << ans << endl;
    return 0;
}

      加上最后那个 while 循环，你的代码就可以 AC 了！

      • 0
        @ 2025-9-9 23:45:52

        C :

        #include<stdio.h>
int main()
{
	char ch,b[1000100];
	long q=0,sum=0;
	 long long d[1000000]={0},s;
	while(scanf("%lld%c",&s,&ch)!=EOF)
	{
			d[q]=s%100000;
			if(ch=='*')
				b[q+1]='*';
			if(b[q-1]=='*'&&(q-1)>=0)
			{
				d[q]=d[q]*d[q-2];
				d[q]=d[q]%100000;
				b[q-1]=' ';
			}
			if(ch=='+')
			{
				sum=sum+d[q];
			}
			q+=2;
			if(ch==10)
			{
				printf("%ld\n",(sum+d[q-2])%10000);
				q=0,sum=0;
			}
	}
	return 0;
}

        C++ :

        #include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
stack<unsigned long> num_stack;
stack<char> oper_stack;
const int READ_OPER =  0;
const int READ_NUM = 1;
const int READ_END = 2;
int main()
{
	int flag = READ_NUM;
	unsigned long t1,t2;
	char oper;
	num_stack.push(1);
	oper_stack.push('*');
	while(1)
	{
		if(flag == READ_NUM)
		{
			if(scanf("%lu",&t1) != 1)
			{
				flag = READ_END;
				continue;
			}
			num_stack.push(t1%10000);
			flag = READ_OPER;
		}
		if(flag == READ_OPER)
		{
			if(scanf("%c",&oper) != 1 || 
				(oper != '+' && oper != '*'))
			{
				flag = READ_END;
				continue;
			}
			if(oper_stack.top() == '*')
			{
				t1 = num_stack.top();
				num_stack.pop();
				t2 = num_stack.top();
				num_stack.pop();
				num_stack.push((t1*t2)%10000);
				//cout << t1 << 'v' << t2 << '-' << (t1*t2)%10000 << endl;
				oper_stack.pop();
			}
			oper_stack.push(oper);
			flag = READ_NUM;
		}
		if(flag == READ_END)
		{
			if(oper_stack.empty())
				break;
			oper = oper_stack.top();
			oper_stack.pop();
			t1 = num_stack.top();
			num_stack.pop();
			t2 = num_stack.top();
			num_stack.pop();
			if(oper == '+')
			{
				num_stack.push((t1+t2)%10000);	
				//cout << t1 << 'v' << t2 << '-' << (t1+t2)%10000 << endl;
			}
			else
			{
				num_stack.push((t1*t2)%10000);
				//cout << t1 << 'v' << t2 << '-' << (t1*t2)%10000 << endl;
			}	
		}
	}
	cout << num_stack.top() << endl;
	return 0;
}

        Pascal :

        var sz:array [1..100001] of integer;
fh:array [1..100001] of char;
s:string;
z:char;
h,i,j:longint;
begin
while not eof do
begin
read(z);
s:='';
while z in ['0'..'9'] do
begin
s:=s+z;
read(z);
end;
i:=i+1;
val(s,j);
sz[i]:=j mod 10000;
fh[i]:=z;
end;
for j:=1 to i do
if fh[j]='*' then
begin
sz[j+1]:=sz[j]*sz[j+1] mod 10000;
sz[j]:=0;
end;
for j:=1 to i do
h:=h+sz[j];
write(h mod 10000);
end.

        Java :

        import java.util.Scanner;
import java.util.Stack;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		ExpDealer ed = new ExpDealer();
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextLine()) {
			String exp = scanner.nextLine();
			if (exp.length() > 0)
				System.out.println(ed.calc(exp));
			else
				System.out.println();
		}
	}
}

class ExpDealer {
	private Stack<Character> stack1;
	private Stack<String> stack2;
	private Stack<BigInteger> result;

	public ExpDealer() {
		super();
		this.stack1 = new Stack<Character>();
		this.stack2 = new Stack<String>();
		this.result = new Stack<BigInteger>();
	}

	private boolean isOp(char c) {
		return c == '+' || c == '-' || c == '*' || c == '/' || c == '#'
				|| c == '(' || c == ')';
	}

	private boolean greater(char op1, char op2) {
		if (op2 == '#' || op2 == '(') {
			return true;
		}
		if (op1 == '*' || op1 == '/') {
			if (op2 == '+' || op2 == '-')
				return true;
		}
		return false;
	}

	private void reset() {
		stack1.clear();
		stack2.clear();
		result.clear();
	}

	private Stack<String> predeal(String expression) {
		expression += '#';
		int length = expression.length();
		String tmp = "";
		stack1.push('#');
		for (int i = 0; i < length; i++) {
			char c = expression.charAt(i);
			if (c == ' ') {
				continue;
			} else if (isOp(c)) {
				if (tmp != "") {
					stack2.push(tmp);
					tmp = "";
				}
				if (c == '(') {
					stack1.push(c);
				} else if (c == ')') {
					char t = stack1.peek();
					while (t != '(') {
						stack2.push(t + "");
						stack1.pop();
						t = stack1.peek();
					}
					stack1.pop();
				} else {
					char t = stack1.peek();
					while (!greater(c, t)) {
						stack2.push(t + "");
						stack1.pop();
						t = stack1.peek();
					}
					stack1.push(c);
				}
			} else {
				tmp += c;
			}
		}
		while (!stack1.empty()) {
			char t = stack1.peek();
			stack2.push(t + "");
			stack1.pop();
		}
		Stack<String> stack = new Stack<String>();
		while (!stack2.empty()) {
			String t = stack2.pop();
			stack.push(t);
		}
		return stack;
	}

	public BigInteger calc(String expression) {
		Stack<String> pre = predeal(expression);
		while (!pre.empty()) {
			String t = pre.pop();
			if (t.equals("#")) {
				continue;
			} else if (isOp(t.charAt(0))) {
				BigInteger num2 = result.pop();
				BigInteger num1 = result.pop();
				if (t.equals("+")) {
					num1 = num1.add(num2);
				} else if (t.equals("-")) {
					num1 = num1.subtract(num2);
				} else if (t.equals("*")) {
					num1 = num1.multiply(num2);
				} else if (t.equals("/")) {
					num1 = num1.divide(num2);
				}
				result.push(num1);
			} else {
				result.push(new BigInteger(t, 10));
			}
		}
		BigInteger ans = result.peek();
		reset();
		return ans.remainder(BigInteger.valueOf(10000));
	}
}
        • 1

        表达式求值

        信息

        ID
        779
        时间
        1000ms
        内存
        128MiB
        难度
        10
        标签
        递交数
        1
        已通过
        1
        上传者
        1. Language
        2. 兼容模式
        3. 主题
        3. Worker 0, 15ms
        4. Powered by Hydro v5.0.0-beta.8 Community