ポーランド記法で書かれた数式は、以下のアルゴリズムにより、スタックを用いて線形時間で計算することができます。

擬似コード

function eval(tokens):
  stack = ()
  for t in tokens:
    stack.push(t)
    while stackの末尾が後ろから順に「数値」「数値」「演算子」:
      b = stack.pop()
      a = stack.pop()
      op = stack.pop()
      result = op(a, b)
      stack.push(result)
  return stack.pop()

このアルゴリズムを用いて、変化前後の 2 個の数式を実際に評価すればよいです。計算量は \(O(N)\) です。言語によっては、負の数の除算の丸め方向に注意してください。

実装例 (C++)

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

bool is_op(string token){
  return token == "+" || token == "-" || token == "*" || token == "/";
}

int main() {
  int n;
  cin >> n;
  vector<string> t(n);
  for(int i=0; i<n; i++) cin >> t[i];
  int k;
  cin >> k;
  vector<int> p(k);
  for(int i=0; i<k; i++){
    cin >> p[i];
    p[i]--;
  }

  auto solve = [&](vector<string> t){
     vector<string> s;
     for(auto token: t){
       s.push_back(token);
       while(s.size() >=3 && !is_op(s[s.size()-1]) && !is_op(s[s.size()-2]) && is_op(s[s.size()-3])){
         string b = s.back(); s.pop_back();
         string a = s.back(); s.pop_back();
         string op = s.back(); s.pop_back();
         if(op == "+"){
           s.push_back(to_string(stoll(a) + stoll(b)));
         }else if(op == "-"){
           s.push_back(to_string(stoll(a) - stoll(b)));
         }else if(op == "*"){
           s.push_back(to_string(stoll(a) * stoll(b)));
         }else if(op == "/"){
           s.push_back(to_string(stoll(a) / stoll(b)));
         }
       }
     }
     return stoll(s.back());
  };
  
  cout << solve(t) << endl;
  for(auto i: p){
    if(t[i] == "+"){
      t[i] = "-";
    }else if(t[i] == "-"){
      t[i] = "+";
    }else if(t[i] == "*"){
      t[i] = "/";
    }else if(t[i] == "/"){
      t[i] = "*";
    }
  }
  cout << solve(t) << endl;
}

実装例 (Python)

def is_op(t):
  return t == '+' or t == '-' or t == '*' or t == '/'

N = int(input())
T = []
for token in input().split():
  if is_op(token):
    T.append(token)
  else:
    T.append(int(token))
K = int(input())
if K > 0:
  P = list(map(int, input().split()))
  P = [p - 1 for p in P]
else:
  P = []

def my_div(a, b):
  if (a < 0) ^ (b < 0):
    return - ((-a) // b)
  return a // b

def solve(T):
  stack = []
  for t in T:
    stack.append(t)
    while len(stack) >= 3 and not is_op(stack[-1]) and not is_op(stack[-2]) and is_op(stack[-3]):
      b = stack.pop()
      a = stack.pop()
      op = stack.pop()
      if op == '+':
        stack.append(a + b)
      elif op == '-':
        stack.append(a - b)
      elif op == '*':
        stack.append(a * b)
      elif op == '/':
        stack.append(my_div(a, b))
  return stack.pop()

print(solve(T))
for p in P:
  if T[p] == '+':
    T[p] = '-'
  elif T[p] == '-':
    T[p] = '+'
  elif T[p] == '*':
    T[p] = '/'
  elif T[p] == '/':
    T[p] = '*'
print(solve(T))